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

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

0.00 Avg rating—0 Votes
Article ID: iaor20072112
Country: United States
Volume: 28
Issue: 4
Start Page Number: 871
End Page Number: 883
Publication Date: Nov 2003
Journal: Mathematics of Operations Research
Authors:
Abstract:

Hierarchies of semidefinite relaxations for 0/1 polytopes have been constructed by Lasserre and by Lovász and Schrijver. 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 Kn.

Reviews

Required fields are marked *. Your email address will not be published.