Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope

Monique Laurent (moniquecwi.nl)

Abstract: Hierarchies of semidefinite relaxations for $0/1$ polytopes have been constructed by Lasserre (2001a) and by Lov\'asz and Schrijver (1991), permitting to find the cut polytope of a graph on $n$ nodes in $n$ steps. We show that $\left\lceil {n\over 2} \right\rceil$ iterations are needed for finding the cut polytope of the complete graph $K_n$.

Keywords: cut polytope, semidefinite relaxation, moment matrix, rank of lift-and-project method

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Mathematics of Operations Research, 28(4):871--883, 2003.

Download:

Entry Submitted: 07/11/2002
Entry Accepted: 07/11/2002
Entry Last Modified: 05/24/2005

Modify/Update this entry