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\).

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