Integrality gaps for Sherali-Adams relaxations

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 n^δ 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^δ.

REFERENCES

• 1: S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis. Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing, vol. 2, pp. 19--51, 2006.
• 2: Sanjeev Arora , László Lovász , Ilan Newman , Yuval Rabani , Yuri Rabinovich , Santosh Vempala, Local versus global properties of metric spaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.41-50, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109563]
• 3: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Local Global Tradeoffs in Metric Embeddings, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.713-723, October 21-23, 2007 [doi>10.1109/FOCS.2007.37]
• 4: Eden Chlamtac, Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.691-701, October 21-23, 2007 [doi>10.1109/FOCS.2007.13]
• 5: Eden Chlamtac , Gyanit Singh, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_5]
• 6: Wenceslas Fernandez de la Vega , Claire Kenyon-Mathieu, Linear programming relaxations of maxcut, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.53-61, January 07-09, 2007, New Orleans, Louisiana
• 7: Konstantinos Georgiou , Avner Magen , Toniann Pitassi , Iannis Tourlakis, Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.702-712, October 21-23, 2007 [doi>10.1109/FOCS.2007.34]
• 8: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 9: . Grötschel, M. Jünger, and G. Reinelt, A cutting plane algorithm for the linear ordering problem. Operations Research 32 (1984), pp. 1195--1220.
• 10: . Grötschel, M. Jünger, and G. Reinelt, On the acyclic subgraph polytope. Mathematical Programming, 32 (1985), pp. 28--42.
• 11: . Grötschel, M. Jünger, and G. Reinelt, Facets of the linear ordering polytope. Mathematical Programming, 32 (1985), pp. 43--60.
• 12: Venkatesan Guruswami , Rajsekar Manokaran , Prasad Raghavendra, Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.573-582, October 25-28, 2008 [doi>10.1109/FOCS.2008.51]
• 13: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 14: Monique Laurent, A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0--1 Programming, Mathematics of Operations Research, v.28 n.3, p.470-496, July 2003 [doi>10.1287/moor.28.3.470.16391]
• 15: L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, vol. 1, pp. 166--190, 1991. SIAM J. Optim., vol. 1, pp. 166--190, 1991.
• 16: Hanif D. Sherali , Warren P. Adams, A hierarchy of relaxation between the continuous and convex hull representations, SIAM Journal on Discrete Mathematics, v.3 n.3, p.411-430, Aug. 1990 [doi>10.1137/0403036]
• 17: Grant Schoenebeck, Linear Level Lasserre Lower Bounds for Certain k-CSPs, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.593-602, October 25-28, 2008 [doi>10.1109/FOCS.2008.74]
• 18: Grant Schoenebeck , Luca Trevisan , Madhur Tulsiani, Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250836]
• 19: Grant Schoenebeck , Luca Trevisan , Madhur Tulsiani, A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.205-216, June 13-March 16, 2007 [doi>10.1109/CCC.2007.2]
• 20: Iannis Tourlakis , Sanjeev Arora, New lower bounds for approximation algorithms in the lovasz-schrijver hierarchy, Princeton University, Princeton, NJ, 2006

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
Sherali-Adams hierarchy, lift-and-project methods, local-global metric spaces