Integrality gaps for sherali-adams relaxations

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

74 Scopus citations

Abstract

We prove strong lower bounds on integrality gaps of Sherali- Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive rounds of lift and project. For MAX CUT and Vertex Cover, these show that even n δ rounds of Sherali-Adams do not yield a better than 2 - ε approximation. The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. We develop a conceptually simple geometric approach to constructing Sherali-Adams gap examples via constructions of consistent local SDP solutions. This geometric approach is surprisingly versatile. We construct Sherali-Adams gap examples for Unique Games based on our construction for MAX CUT together with a parallel repetition like procedure. This in turn allows us to obtain Sherali-Adams gap examples for any problem that has a Unique Games based hardness result (with some additional conditions on the reduction from Unique Games). Using this, we construct 2-ε gap examples for Maximum Acyclic Subgraph that rules out any family of linear constraints with support at most nδ.

Original languageEnglish (US)
Title of host publicationSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages283-292
Number of pages10
DOIs
StatePublished - Nov 9 2009
Event41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States
Duration: May 31 2009Jun 2 2009

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other41st Annual ACM Symposium on Theory of Computing, STOC '09
CountryUnited States
CityBethesda, MD
Period5/31/096/2/09

Keywords

  • Lift-and-project methods
  • Local global metric spaces
  • Sherali-Adams hierarchy

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Integrality gaps for sherali-adams relaxations'. Together they form a unique fingerprint.

Cite this