- 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/2000Entry Accepted: 10/12/2000Entry Last Modified: 06/24/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.