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 条
  • [41] A note on greedy algorithms for the maximum weighted independent set problem
    Sakai, S
    Togasaki, M
    Yamazaki, K
    DISCRETE APPLIED MATHEMATICS, 2003, 126 (2-3) : 313 - 322
  • [42] GreedyMAX-type Algorithms for the Maximum Independent Set Problem
    Borowiecki, Piotr
    Goering, Frank
    SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2011, 6543 : 146 - 156
  • [43] GreedyMAX-type algorithms for the maximum independent set problem
    Department of Algorithms and System Modeling, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland
    不详
    Lect. Notes Comput. Sci., (146-156):
  • [44] On Completeness of SDP-Based Barrier Certificate Synthesis over Unbounded Domains
    Wu, Hao
    Feng, Shenghua
    Gang, Ting
    Wang, Jie
    Xia, Bican
    Zhan, Naijun
    FORMAL METHODS, PT II, FM 2024, 2025, 14934 : 248 - 266
  • [45] PEP analysis of SDP-based non-coherent signal detection
    Stojnic, Mihailo
    Hassibi, Babak
    Vikalo, Haris
    2007 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-7, 2007, : 2916 - 2920
  • [46] A reduction from an LWE problem to maximum independent set problems
    Yasuhito Kawano
    Scientific Reports, 13
  • [47] Approximating maximum independent sets in uniform hypergraphs
    Hofmeister, T
    Lefmann, H
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1998, 1998, 1450 : 562 - 570
  • [48] A METAHEURISTIC ALGORITHM FOR LARGE MAXIMUM WEIGHT INDEPENDENT SET PROBLEMS
    Dong, Yuanyuan
    Goldberg, Andrew V.
    Noe, Alexander
    Parotsidis, Nikos
    Resende, Mauricio G.C.
    Spaen, Quico
    arXiv, 2022,
  • [49] A reduction from an LWE problem to maximum independent set problems
    Kawano, Yasuhito
    SCIENTIFIC REPORTS, 2023, 13 (01)
  • [50] THE COLORING AND MAXIMUM INDEPENDENT SET PROBLEMS ON PLANAR PERFECT GRAPHS
    HSU, WL
    JOURNAL OF THE ACM, 1988, 35 (03) : 535 - 563
12345