Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
From MaRDI portal
Publication:2784415
DOI10.1137/S1052623400379371zbMath1068.90587MaRDI QIDQ2784415
Publication date: 23 April 2002
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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
This page was built for publication: Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure