Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

ABSTRACT

Lovász and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for max-cu , max-3sat, and sparsest cut).We prove strong inapproximability results in this model for well-known problems such as max-3sat, hypergraph vertex cover and set cover. We show that the relaxations produced by as many as Ω(n) rounds of the LS+ procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS+ approach gives even slightly subexponential approximation algorithms for these problems.We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

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: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 3: 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
• 4: Irit Dinur , Venkatesan Guruswami , Subhash Khot , Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780629]
• 5: Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509915]
• 6: Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
• 7: Uriel Feige , Robert Krauthgamer, The Probable Value of the Lovász-Schrijver Relaxations for Maximum Independent Set, SIAM Journal on Computing, v.32 n.2, p.345-370, 2003 [doi>10.1137/S009753970240118X]
• 8: Michel X. Goemans , Levent Tunçel, When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?, Mathematics of Operations Research, v.26 n.4, p.796-815, November 2001 [doi>10.1287/moor.26.4.796.10012]
• 9: Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
• 10: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 11: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
• 12: L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1(2):166--190, May 1991.
• 13: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 14: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Theory

Keywords:
Lovász-Schrijver matrix cuts, inapproximability, integrality gaps