  


Semidefinite relaxations for MaxCut
Monique Laurent (moniquecwi.nl) Abstract: We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lov\'asz and Schrijver and of Lasserre. We show that the tightest relaxation is obtained when aplying the Lasserre construction to the node formulation of the maxcut problem. This relaxation $Q_t(G)$ can be defined as the projection on the edge subspace of the set $\FF_t(n)$, which consists of the matrices indexed by all subsets of $[1,n]$ of cardinality $\le t+1$ with the same parity as $t+1$ and having the property that their $(I,J)$th entry depends only on the symmetric difference of the sets $I$ and $J$. The set $\FF_0(n)$ is the basic semidefinite relaxation of maxcut consisting of the semidefinite matrices of order $n$ with an all ones diagonal, while $\FF_{n2}(n)$ is the $2^{n1}$dimensional simplex with the cut matrices as vertices. We show the following geometric properties: If $Y\in \FF_t(n)$ has rank $\le t+1$, then $Y$ can be written as a convex combination of at most $2^t$ cut matrices, extending a result of Anjos and Wolkowicz for the case $t=1$; any $2^{t+1}$ cut matrices form a face of $\FF_t(n)$ for $t=0,1,n2$. The class $\LL_t$ of the graphs $G$ for which $Q_t(G)$ is the cut polytope of $G$ is shown to be closed under taking minors. The graph $K_7$ is a forbidden minor for membership in $\LL_2$, while $K_3$ and $K_5$ are the only minimal forbidden minors for the classes $\LL_0$ and $\LL_1$, respectively. Keywords: cut polytope, semidefinite relaxation, liftandproject, maxcut problem Category 1: Integer Programming Category 2: Linear, Cone and Semidefinite Programming Category 3: Combinatorial Optimization Citation: In The Sharpest Cut: The Impact of Manfred Padberg and His Work. M. Gr\"otschel, ed., pages 257290, MPSSIAM Series in Optimization 4, 2004. Download: [Postscript] Entry Submitted: 10/18/2001 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  