Skip to main content
SpringerLink
Log in

Connections between semidefinite relaxations of the max-cut and stable set problems

  • Published:
Mathematical Programming Submit manuscript

Abstract

We describe links between a recently introduced semidefinite relaxation for the max-cut problem and the well known semidefinite relaxation for the stable set problem underlying the Lovász’s theta function. It turns out that the connection between the convex bodies defining the semidefinite relaxations mimics the connection existing between the corresponding polyhedra. We also show how the semidefinite relaxations can be combined with the classical linear relaxations in order to obtain tighter relaxations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Balas, S. Ceria and G. Cornuejols, A lift-and-project cutting plane algorithm for mixed 0–1 programs,Mathematical Programming 58 (1993) 295–324.

    Article  MathSciNet  Google Scholar 

  2. E. Balas, S. Ceria, G. Cornuejols and G. Pataki, Polyhedral methods for the maximum clique problem, Technical Report, Carnegie Mellon University, Pittsburgh, PA, 1994.

    Google Scholar 

  3. E. Balas, S. Ceria, G. Cornuejols and G. Pataki, Updated semi-definite constraints, Technical Report, Carnegie Mellon University, Pittsburgh, PA, 1994.

    Google Scholar 

  4. F. Barahona, On cuts and matchings in planar graphs,Mathematical Programming 60 (1993) 53–68.

    Article  MathSciNet  Google Scholar 

  5. F. Barahona and A.R. Mahjoub, On the cut polytope,Mathematical Programming 36 (1986) 157–173.

    Article  MATH  MathSciNet  Google Scholar 

  6. W.W. Barrett, C.R. Johnson and R. Loewy, The real positive definite completion problem: Cycle completability,Memoirs of the AMS 584 (1996).

  7. C. Delorme and S. Poljak, Laplacian eigenvalues and the max-cut problem,Mathematical Programming 63 (1993) 557–574.

    Article  MathSciNet  Google Scholar 

  8. C. De Simone, The cut polytope and the boolean quadric polytope,Discrete Mathematics 79 (1989/1990) 71–75.

    Article  MathSciNet  Google Scholar 

  9. U. Feige and M.X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, in:Proceedings of the Israel Symposium on Theory of Computing and Systems, 1995, 182–189.

  10. A.M.H. Gerards and F.B. Shepherd, The characterization of graphs with all subgraphst-perfect, Research Report LSE-CDAM-96-09, Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science, June 1996.

  11. M.X. Goemans and D.P. Williamson, .878-approximation algorithms for MAX CUT and MAX 2SAT, in:Proceedings of the 26th Annual Symposium on Theory of Computing, Montréal (1994) 422–431.

  12. R. Grone, C.R. Johnson, E.M. Sá and H. Wolkowicz, Positive definite completions of partial hermitian matrices,Linear Algebra and its Applications 58 (1984) 109–124.

    Article  MATH  MathSciNet  Google Scholar 

  13. M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988).

    MATH  Google Scholar 

  14. P.L. Hammer, Some network flow problems solved with pseudo-boolean programming,Operations Research 13 (1965) 388–399.

    Article  MathSciNet  Google Scholar 

  15. P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0–1 optimization,Mathematical Programming 28 (1984) 121–155.

    Article  MATH  MathSciNet  Google Scholar 

  16. C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz, A primal-dual interior point method for the max-min eigenvalue problem,SIAM Journal on Optimization 6 (1996) 342–361.

    Article  MATH  MathSciNet  Google Scholar 

  17. J. Kleinberg and M. Goemans, The Lovász theta function and a semidefinite programming relaxation of vertex cover,SIAM Journal on Discrete Mathematics, to appear.

  18. M. Laurent, The real positive semidefinite completion problem for series-parallel graphs,Linear Algebra and its Applications 252 (1997) 347–366.

    Article  MATH  MathSciNet  Google Scholar 

  19. M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope,Linear Algebra and its Applications 223/224 (1995) 439–461.

    Article  MathSciNet  Google Scholar 

  20. M. Laurent and S. Poljak, On the facial structure of the set of correlation matrices,SIAM Journal on Matrix Analysis and Applications 17 (1996) 530–547.

    Article  MATH  MathSciNet  Google Scholar 

  21. L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization,SIAM Journal of Optimization 1 (2) (1991) 166–190.

    Article  MATH  Google Scholar 

  22. M. Padberg, The boolean quadric polytope: Some characteristics, facets and relatives,Mathematical Programming 45 (1989) 139–172.

    Article  MATH  MathSciNet  Google Scholar 

  23. S. Poljak and F. Rendl, Nonpolyhedral relaxation of graph-bisection problems,SIAM Journal on Optimization 5 (1995) 467–487.

    Article  MATH  MathSciNet  Google Scholar 

  24. S. Poljak and Zs. Tuza, On the expected relative error of the polyhedral approximation of the max-cut,Operations Research Letters 16 (1994) 191–198.

    Article  MATH  MathSciNet  Google Scholar 

  25. A. Schrijver, A comparison of the Delsarte and Lovász bound,IEEE Transactions on Information Theory 25 (1979) 425–429.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIENS - Ecole Normale Supérieure, 45 rue d’Ulm, 75230, Paris cedex 05, France

    Monique Laurent

  2. Fakultät für Mathematik und Informatik, Universität Passau, Innstrasse 33, 94030, Passau, Germany

    Svatopluk Poljak

  3. Technische Universität Graz, Institut für Mathematik, Kopernikusgasse 24, A-8010, Graz, Austria

    Franz Rendl

Authors
  1. Monique Laurent
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Svatopluk Poljak
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Franz Rendl
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was done while the author visited CWI, Amsterdam, The Netherlands.

Svata Poljak untimely deceased in April 1995. We shall both miss Svata very much. Svata was an excellent colleague, from whom we learned a lot of mathematics and with whom working was always a very enjoyable experience; above all, Svata was a very nice person and a close friend of us.

The research was partly done while the author visited CWI, Amsterdam, in October 1994 with a grant fom the Stieltjes Institute, whose support is gratefully acknowledged. Partially supported also by GACR 0519.

Research support by Christian Doppler Laboratorium für Diskrete Optimierung.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laurent, M., Poljak, S. & Rendl, F. Connections between semidefinite relaxations of the max-cut and stable set problems. Mathematical Programming 77, 225–246 (1997). https://doi.org/10.1007/BF02614436

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02614436

Keywords

Search

Navigation