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

Monique Laurent (moniquecwi.nl)

Abstract: 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 suffice instead of the $m$ (number of edges) iterations required in general and, under some assumption, $n-\alpha(G)-3$ iterations suffice. The exact number of needed iterations is determined for small $n\le 7$ by a detailed analysis of the new relaxations. If positive semidefiniteness is added to the construction, then one finds in one iteration a relaxation of the cut polytope which is tighter than its basic semidefinite relaxation and than another one introduced recently by Anjos and Wolkowicz \cite{AW00}. We also show how the Lov\'asz-Schrijver relaxations for the stable set polytope of $G$ can be strenghtened using the corresponding relaxations for the cut polytope of the graph $G^\nabla$ obtained from $G$ by adding a node adjacent to all nodes of $G$.

Keywords: lift-and-project, semidefinite relaxation, linear relaxation, max-cut

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: SIAM Journal on Optimization, 12:345--375, 2001

Download:

Entry Submitted: 10/12/2000
Entry Accepted: 10/12/2000
Entry Last Modified: 06/24/2002

Modify/Update this entry