# zbMATH — the first resource for mathematics

Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. (English) Zbl 1082.90085
Summary: Hierarchies of semidefinite relaxations for $$0/1$$ polytopes have been constructed by J. B. Lasserre [SIAM J. Optim. 11, No. 3, 796–817 (2001; Zbl 1010.90061)] and by L. Lovász and A. Schrijver [SIAM J. Optim. 1, No. 2, 166–190 (1991; Zbl 0754.90039)]. The cut polytope of a graph on $$n$$ nodes can be expressed as a projection of such a semidefinite relaxation after at most $$n$$ steps. We show that $$[n/2]$$ iterations are needed for finding the cut polytope of the complete graph $$K_n$$.

##### MSC:
 90C22 Semidefinite programming 05C85 Graph algorithms (graph-theoretic aspects) 90C09 Boolean programming 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: