SDP-based algorithms for maximum independent set problems on hypergraphs

被引：4
|
作者：
Agnarsson, Geir [1 ]
Halldorsson, Magnus M. [2 ]
Losievskaja, Elena [2 ]
机构：
[1] George Mason Univ, Dept Math Sci, Fairfax, VA 22030 USA
[2] Reykjavik Univ, Sch Comp Sci, IS-101 Reykjavik, Iceland
来源：
THEORETICAL COMPUTER SCIENCE | 2013年 / 470卷
关键词：
Independent sets; Hypergraphs; Approximation algorithms; APPROXIMATION ALGORITHMS; GRAPHS;
D O I：
10.1016/j.tcs.2012.11.025
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper deals with approximations of maximum independent sets in non-uniform hypergraphs of low degree. We obtain the first performance ratio that is sublinear in terms of the maximum or average degree of the hypergraph. We extend this to the weighted case and give a O((D) over bar log log (D) over bar /log (D) over bar) bound, where (D) over bar is the average weighted degree in a hypergraph, matching the best bounds known for the special case of graphs. Our approach is to use an semi-definite technique to sparsify a given hypergraph and then apply combinatorial algorithms to find a large independent set in the resulting sparser instance. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：1 / 9
页数：9
相关论文
共 50 条
  • [1] SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
    Agnarsson, Geir
    Halldorsson, Magnus M.
    Losievskaja, Elena
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2009, 5555 : 12 - +
  • [2] Computational Experience with a SDP-Based Algorithm for Maximum Cut with Limited Unbalance
    Galbiati, Giulia
    Gualandi, Stefano
    Maffioli, Francesco
    NETWORKS, 2010, 55 (03) : 247 - 255
  • [3] Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms
    Wu, Wentao
    Chan, Wai Kin Victor
    Chi, Lei
    Gong, Zhiguo
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2017, 34 (03)
  • [4] A new optimization in SDP-based learning
    Hu, En-Liang
    Wang, Bo
    NEUROCOMPUTING, 2019, 365 : 10 - 20
  • [5] Exact Algorithms for Maximum Independent Set
    Xiao, Mingyu
    Nagamochi, Hiroshi
    ALGORITHMS AND COMPUTATION, 2013, 8283 : 328 - 338
  • [6] Exact algorithms for maximum independent set
    Xiao, Mingyu
    Nagamochi, Hiroshi
    INFORMATION AND COMPUTATION, 2017, 255 : 126 - 146
  • [7] EFFICIENT ALGORITHMS FOR THE MAXIMUM WEIGHT CLIQUE AND MAXIMUM WEIGHT INDEPENDENT SET PROBLEMS ON PERMUTATION GRAPHS
    CHANG, MS
    WANG, FH
    INFORMATION PROCESSING LETTERS, 1992, 43 (06) : 293 - 295
  • [8] Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs
    Matsui, T
    DISCRETE AND COMPUTATIONAL GEOMETRY, 2000, 1763 : 194 - 200
  • [9] SDP-Based Moment Closure for Epidemic Processes on Networks
    Chen, Ximing
    Ogura, Masaki
    Preciado, Victor M.
    IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING, 2020, 7 (04): : 2850 - 2865
  • [10] Iterative quantum algorithms for maximum independent set
    Brady, Lucas T.
    Hadfield, Stuart
    PHYSICAL REVIEW A, 2024, 110 (05)
12345