max-cut problem – Page 3 – Optimization Online

Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem

Published: 2001/02/09, Updated: 2002/06/13

Combinatorial Optimization, Semi-definite Programming cut polytope, lagrangian relaxation, max-cut problem, metric polytope, semidefinite programming

In this paper we study two strengthened semidefinite programming relaxations for the Max-Cut problem. Our results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. We prove that the first relaxation provides a strengthening of the Goemans-Williamson relaxation. The second relaxation is a further tightening of the first … Read more

Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\’asz-Schrijver Lift-and-Project Procedure

Published: 2000/10/12, Updated: 2002/06/24

Monique Laurent

Combinatorial Optimization, Linear, Cone and Semidefinite Programming lift-and-project, linear relaxation, max-cut problem, semidefinite relaxation

We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations … Read more