  


Tighter Linear and Semidefinite Relaxations for MaxCut Based on the Lov\'aszSchrijver LiftandProject Procedure
Monique Laurent (moniquecwi.nl) Abstract: We study how the liftandproject 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, $n4$ 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\'aszSchrijver 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: liftandproject, semidefinite relaxation, linear relaxation, maxcut Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming Citation: SIAM Journal on Optimization, 12:345375, 2001 Download: Entry Submitted: 10/12/2000 Modify/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  