Abstract
The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lovász.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barahona F.: The max-cut problem on graphs not contractible to K 5. Oper. Res. Lett. 2, 107–111 (1983)
Barahona F., Grötschel M.: On the cycle polytope of a binary matroid. J. Combinatorial Theory Ser. B 40(1), 40–62 (1986)
Bochnak J., Coste M., Roy M.-F.: Real Algebraic Geometry. Springer, Berlin (1998)
Cox D.A., Little J.B., O’Shea D.B.: Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Berlin (2005)
Deza M.M., Laurent M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)
Edmonds J., Johnson E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88–124 (1973)
Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, Publishers, San Francisco (1979)
Goemans M.X., Williamson D.: Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
Gouveia, J., Parrilo, P.A., Thomas, R.: Theta bodies for polynomial ideals, preprint. arXiv:0809.3480 (2008)
Grötschel M., Truemper K.: Master polytopes for cycles of binary matroids. Linear Algebra Appl. 114/114, 523–540 (1989)
Grötschel M., Truemper K.: Decomposition and optimization over cycles in binary matroids. J. Combinatotorial Theory B 46(3), 306–337 (1989)
Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0–1 programs. In: Aardal, K., Gerards, A.M.H. (eds.) Lecture Notes in Computer Science, vol. 2081, pp. 293–303 (2001)
Laurent M.: A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3), 470–496 (2003)
Laurent M.: Lower bound for the number of iterations in semidefinite relaxations for the cut polytope. Math. Oper. Res. 28(4), 871–883 (2003)
Laurent, M.: Semidefinite relaxations for max-cut. In: The sharpest cut, MPS/SIAM Ser. Optim., pp. 257–290. SIAM, Philadelphia, PA (2004)
Laurent M.: Semidefinite representations for finite varieties. Math. Program. 109, 1–26 (2007)
Laurent M., Rendl F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds) Handbook on Discrete Optimization, pp. 393–514. Elsevier B.V., Amsterdam (2005)
Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1–7 (1979)
Lovász, L.: Semidefinite programs and combinatorial optimization. In: Recent advances in algorithms and combinatorics, volume 11 of CMS Books Math./Ouvrages Math. SMC, pp. 137–194. Springer, New York (2003)
Lovász L., Schrijver A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190 (1991)
Oxley J.G.: Matroid Theory. Oxford University Press, Oxford (1992)
Parrilo P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Prog. 96(2, Ser. B), 293–320 (2003)
Sherali H.D., Adams W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3, 411–430 (1990)
Sullivant S.: Compressed polytopes and statistical disclosure limitation. Tohoku Math. J. (2) 58(3), 433–445 (2006)
Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems. PhD thesis. Alpen-Adria-Universität Klagenfurt (2006)
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Gouveia, Parrilo and Thomas were partially supported by the NSF Focused Research Group grants DMS-0757371 and DMS-0757207. Gouveia was also partially supported by Fundação para a Ciência e Tecnologia and Thomas by the Robert R. and Elaine K. Phelps Endowment at the University of Washington.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Gouveia, J., Laurent, M., Parrilo, P.A. et al. A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs. Math. Program. 133, 203–225 (2012). https://doi.org/10.1007/s10107-010-0425-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0425-z
Keywords
- Theta bodies
- Binary matroid
- Cycle ideal
- Cuts
- Cut polytope
- Combinatorial moment matrices
- Semidefinite relaxations
- TH1-exact