Optimization Online


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

Monique Laurent (monique***at***cwi.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.


Entry Submitted: 07/11/2002
Entry Accepted: 07/11/2002
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