- Semidefinite relaxations for Max-Cut 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 max-cut 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 max-cut consisting of the semidefinite matrices of order $n$ with an all ones diagonal, while $\FF_{n-2}(n)$ is the $2^{n-1}$-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,n-2$. 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, lift-and-project, max-cut 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 257-290, MPS-SIAM Series in Optimization 4, 2004. Download: [Postscript]Entry Submitted: 10/18/2001Entry Accepted: 10/18/2001Entry Last Modified: 05/24/2005Modify/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.