TY - JOUR
T1 - SDP-based algorithms for maximum independent set problems on hypergraphs
AU - Agnarsson, Geir
AU - Halldórsson, Magnús M.
AU - Losievskaja, Elena
PY - 2013/1/28
Y1 - 2013/1/28
N2 - 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(DloglogD/logD) bound, where D 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.
AB - 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(DloglogD/logD) bound, where D 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.
KW - Approximation algorithms
KW - Hypergraphs
KW - Independent sets
UR - http://www.scopus.com/inward/record.url?scp=84872034580&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.11.025
DO - 10.1016/j.tcs.2012.11.025
M3 - Article
AN - SCOPUS:84872034580
SN - 0304-3975
VL - 470
SP - 1
EP - 9
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -