Connection between semidefinite relaxations of the max-cut and stable set problems
From MaRDI portal
Publication:1373736
zbMATH Open0888.90128MaRDI QIDQ1373736FDOQ1373736
Authors: Monique Laurent, Svatopluk Poljak, Franz Rendl 
Publication date: 8 June 1998
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 2196288
- Strengthened semidefinite programming relaxations for the max-cut problem.
- A tight semidefinite relaxation of the MAX CUT problem
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Exploring the relationship between max-cut and stable set relaxations
Cited In (22)
- Mathematical programming models and exact algorithms
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- A Derivation of Lovász' Theta via Augmented Lagrange Duality
- Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Exploring the relationship between max-cut and stable set relaxations
- Semidefinite programming in combinatorial optimization
- The real positive semidefinite completion problem for series-parallel graphs
- Semidefinite programming and combinatorial optimization
- Strengthened semidefinite programming relaxations for the max-cut problem.
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- Semidefinite programming and constraint programming
- Computational Experience with Stable Set Relaxations
- Combining semidefinite and polyhedral relaxations for integer programs
- Bipartite sandwiches: Semidefinite relaxations for maximum biclique
- On a positive semidefinite relaxation of the cut polytope
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Exploiting semidefinite relaxations in constraint programming
- SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
- Asymptotic Bayesian structure learning using graph supports for Gaussian graphical models
- The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling
- On Integrality in Semidefinite Programming for Discrete Optimization
This page was built for publication: Connection between semidefinite relaxations of the max-cut and stable set problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1373736)
