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