Optimization Online


Semidefinite relaxations for Max-Cut

Monique Laurent (monique***at***cwi.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/2001
Entry Accepted: 10/18/2001
Entry Last Modified: 05/24/2005

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