Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
verfasst von : Siavosh Benabbas, Avner Magen
Erschienen in: Integer Programming and Combinatorial Optimization
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
We show how under certain conditions one can extend constructions of integrality gaps for semidefinite relaxations into ones that hold for stronger systems: those SDP to which the so-called
k
-level constraints of the Sherali-Adams hierarchy are added. The value of
k
above depends on properties of the problem. We present two applications, to the
Quadratic Programming
problem and to the
MaxCutGain
problem.
Our technique is inspired by a paper of Raghavendra and Steurer [Raghavendra and Steurer, FOCS 09] and our result gives a doubly exponential improvement for
Quadratic Programming
on another result by the same authors [Raghavendra and Steurer, FOCS 09]. They provide tight integrality-gap for the system above which is valid up to
k
= (loglog
n
)
Ω(1)
whereas we give such a gap for up to
k
=
n
Ω(1)
.