Optimization Online


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

Monique Laurent (monique***at***cwi.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society