Sherali-adams relaxations of the matching polytope

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sherali-adams relaxations of the matching polytope

Full text

Pdf (442 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Optimization table of contents

Pages 293-302

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Claire Mathieu	Brown University, Providence, RI, USA
Alistair Sinclair	University of California, Berkeley, CA, USA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 52, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1536414.1536456 What is a DOI?

ABSTRACT

We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1+1/k for the integrality gap after k rounds of this hierarchy. The result is derived by a detailed analysis of the LP after k rounds applied to the complete graph K_{2d+1}. We give an explicit recurrence for the value of this LP, and hence show that its gap exhibits a "phase transition," dropping from close to its maximum value 1+1/2d to close to 1 around the threshold k=2d-Θ(√d). We also show that the rank of the matching polytope (i.e., the number of Sherali-Adams rounds until the integer polytope is reached) is exactly 2d-1.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Néstor E. Aguilera , Silvia M. Bianchi , Graciela L. Nasini, Lift and project relaxations for the matching and related polytopes, Discrete Applied Mathematics, v.134 n.1-3, p.193-212, 05 January 2004 [doi>10.1016/S0166-218X(03)00337-8]
	2	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]
	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	S.Arora, B.Bollobas, L.Lovasz and I.Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing 2 (2006), pp. 19--51.
	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	C.Berge. Sur le couplage maximum d'un graphe. C.R. Acad. Sci. Paris Ser. I Math. 247 (1958), pp.258--259.
	7	J.A. Bondy , U.S.R Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008
	8	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
	9	Moses Charikar, On semidefinite programming relaxations for graph coloring and vertex cover, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.616-620, January 06-08, 2002, San Francisco, California
	10	Moses Charikar , Konstantin Makarychev , Yury Makarychev, Integrality gaps for Sherali-Adams relaxations, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536455]
	11	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]
	12	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]
	13	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
	14	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]
	15	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]
	16	D.Grigoriev, E.Hirsch and D.Pasechnik. Complexity of semialgebraic proofs. Moscow Mathematical Journal 2 (2002), pp. 647--679.
	17	Sung-Pil Hong , Levent Tunçel, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, Discrete Applied Mathematics, v.156 n.1, p.25-41, January, 2008 [doi>10.1016/j.dam.2007.07.021]
	18	A.Kojevnikov and D.Itsykson. Lower bounds for static Lovasz--Schrijver calculus proofs for Tseitin tautologies. Proc. ICALP 2006, pp. 323--334.
	19	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]
	20	Jean B. Lasserre, An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.293-303, June 13-15, 2001
	21	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]
	22	L.Lovasz and A.Schrijver. Cones of matrices and set--functions and 0-1 optimization. SIAM J. Optimization 1 (1991), pp. 166--190.
	23	Toniann Pitassi , Nathan Segerlind, Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.355-364, January 04-06, 2009, New York, New York
	24	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]
	25	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]
	26	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]
	27	Tamon Stephen , Levent Tuncel, On a Representation of the Matching Polytope Via Semidefinite Liftings, Mathematics of Operations Research, v.24 n.1, p.1-7, January 1999 [doi>10.1287/moor.24.1.1]
	28	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]