Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope
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$. CitationMathematics … Read more