Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure

DOI10.1137/S1052623400379371zbMath1068.90587MaRDI QIDQ2784415

Monique Laurent

Publication date: 23 April 2002

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

stable set polytopecut polytopelinear relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items (7)

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Spectral bounds for the maximum cut problem ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting

Uses Software

• SDPpack

This page was built for publication: Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure