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

MaRDI QIDQ1373736zbMATH OpenFDO

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)

zbMATH Keywords

semidefinite relaxationstable set problemmax-cut problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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)

• On Integrality in Semidefinite Programming for Discrete Optimization
• 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
• Semidefinite programming in combinatorial optimization
• Exploring the relationship between max-cut and stable set relaxations
• Semidefinite programming and combinatorial optimization
• The real positive semidefinite completion problem for series-parallel graphs
• An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
• Strengthened semidefinite programming relaxations for the max-cut 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
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• On a positive semidefinite relaxation of the cut polytope
• 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 1 programs via scaling

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)