This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Cheung, K. K. H. Search for Related Content

Computation of the Lasserre Ranks of Some Polytopes

School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario K1S 5B6, Canada
kcheung{at}math.carleton.ca

Over the years, various lift-and-project methods have been proposed to construct hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope P ⁿ that converge to P in n steps. Many such methods have been shown to require n steps in the worst case. In this paper, we show that the method of Lasserre also requires n steps in the worst case.

Key Words: 0–1 polytope; lift and project; semidefinite relaxation; Lasserre rank
History: Received: February 1, 2005; revision received: February 25, 2006;