Computation of the Lasserre ranks of some polytopes

0.00 Avg rating—0 Votes

Article ID:	iaor200948527
Country:	United States
Volume:	32
Issue:	1
Start Page Number:	88
End Page Number:	94
Publication Date:	Feb 2007
Journal:	Mathematics of Operations Research
Authors:	Cheung Kevin K H
Keywords:	polytopes

Abstract:

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.

Reviews

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