Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
verfasst von : Geir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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(\bar{D} \log\log \bar{D}/\log \bar{D})$
bound, where
$\bar{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.