Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

ABSTRACT

We study linear programming relaxations of Vertex Cover and Max Cutarising from repeated applications of the "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove thatthe integrality gap remains at least 2-ε after Ω_ε(log n) rounds, where n is the number ofvertices, and Tourlakis proves that integrality gap remains at least 1.5-ε after Ω((log n)²) rounds. Fernandez de laVega and Kenyon prove that the integrality gap of Max Cut is at most 12 + ε after any constant number of rounds. (Theirresult also applies to the more powerful Sherali-Adams method.

We prove that the integrality gap of Vertex Cover remains at least 2-ε after Ω_ε (n) rounds, and that theintegrality gap of Max Cut remains at most 1/2 +ε after Ω_ε(n) rounds.

REFERENCES

• 1: Sanjeev Arora , Béla Bollobás , László Lovász, Proving Integrality Gaps without Knowing the Linear Program, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.313-322, November 16-19, 2002
• 2: S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19--51, 2006.
• 3: I. Dinur and S. Safra. On the hardness of approximating minimum vertex-cover. Annals of Mathematics, 162(1):439--486, 2005.
• 4: W. Fernandez de la Vega and C. Kenyon-Mathieu. Linear programming relaxations of Maxcut. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2007. To appear.
• 5: 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]
• 6: S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. In Proceedings of the 18th IEEE Conference on Computational Complexity, 2003.
• 7: L. Lovasz and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM J. on Optimization, 1(12):166--190, 1991.
• 8: G. Schoenebeck, L. Trevisan, and M. Tulsiani. Tight integrality gaps for lovasz-schrijver lp relaxations of vertex cover and max cut. Technical Report TR06-132, Electronic Colloquium on Computational Complexity, 2006.
• 9: 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]
• 10: Iannis Tourlakis, New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.170-182, July 16-20, 2006 [doi>10.1109/CCC.2006.28]

INDEX TERMS

General Terms:
Algorithms, Theory

Keywords:
Lovasz-Schrijver hierarchy, approximation algorithms, integrality gap, linear programming