Linear programming relaxations of maxcut

ABSTRACT

It is well-known that the integrality gap of the usual linear programming relaxation for Maxcut is 2 - ε. For general graphs, we prove that for any ε and any fixed bound k, adding linear constraints of support bounded by k does not reduce the gap below 2 - ε. We generalize this to prove that for any ε and any fixed bound k, strengthening the usual linear programming relaxation by doing κ rounds of Sherali-Adams lift-and-project does not reduce the gap below 2 - ε. On the other hand, we prove that for dense graphs, this gap drops to 1 + ε after adding all linear constraints of support bounded by some constant depending on ε.

REFERENCES

• 1: Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060634]
• 2: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences, v.67 n.2, p.212-243, September 2003 [doi>10.1016/S0022-0000(03)00008-4]
• 3: 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
• 4: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP -hard problems, Journal of Computer and System Sciences, v.58 n.1, p.193-210, Feb. 1999 [doi>10.1006/jcss.1998.1605]
• 5: Egon Balas , Sebastián Ceria , Gérard Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming: Series A and B, v.58 n.3, p.295-324, Feb. 25, 1993 [doi>10.1007/BF01581273]
• 6: Joshua Buresh-Oppenheim , Nicola Galesi , Shlomo Hoory , Avner Magen , Toniann Pitassi, Rank Bounds and Integrality Gaps for Cutting Planes Procedures, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.318, October 11-14, 2003
• 7: Michel Deza and Monique Laurent Geometry of Cuts and Metrics. Springer-Verlag, Berlin, 1997.
• 8: Uriel Feige , Gideon Schechtman, On the integrality ratio of semidefinite relaxations of MAX CUT, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.433-442, July 2001, Hersonissos, Greece [doi>10.1145/380752.380837]
• 9: W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
• 10: A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
• 11: A. M. Frieze and R. Kannan Quick Approximation to matrices and applications, Combinatorica 19 (2) (1999) pp 175--200.
• 12: 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]
• 13: O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
• 14: Howard Karloff, How good is the Goemans-Williamson MAX CUT algorithm?, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.427-434, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237990]
• 15: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 16: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 17: 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]
• 18: Jean B. Lasserre, An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs, SIAM Journal on Optimization, v.12 n.3, p.756-769, 2002 [doi>10.1137/S1052623400380079]
• 19: L. Lovasz and A. Schrijver, Cones of matrices and setfunctions, and 0-1 optimization, SIAM J. of Optimization 1 (1990) 166--190.
• 20: S Poljak and Zs. Tuza. On the expected relative error of the polyhedral approximation of the max-cut, Oper. Res. Letters 16 (1994) 191--198.
• 21: 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]