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

zbMath0888.90128MaRDI QIDQ1373736

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

max-cut problemsemidefinite relaxationstable set problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Mathematical Programming Models and Exact Algorithms, A Derivation of Lovász' Theta via Augmented Lagrange Duality, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, Semidefinite programming in combinatorial optimization, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Combining semidefinite and polyhedral relaxations for integer programs, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, On Integrality in Semidefinite Programming for Discrete Optimization, The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling, The real positive semidefinite completion problem for series-parallel graphs, Semidefinite programming and combinatorial optimization, Exploiting semidefinite relaxations in constraint programming, Exploring the relationship between max-cut and stable set relaxations, Asymptotic Bayesian structure learning using graph supports for Gaussian graphical models, Semidefinite Programming and Constraint Programming, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem