Computation of the Lasserre Ranks of Some Polytopes
Computation of the Lasserre Ranks of Some Polytopes
复制标题
一些多胞形的拉塞尔秩的计算
DOI：
10.1287/moor.1060.0212
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Kevin K. H. Cheung
中科院分区：
文献类型：
--
作者：
Kevin K. H. Cheung
多年来，人们已经提出了各种提升和投影方法来构造以n步收敛于P的0-1多面体P⊆Rn的连续线性或半定松弛系。许多这样的方法已经被证明在最坏的情况下需要n个步骤。在本文中，我们证明了在最坏的情况下，拉瑟尔方法也需要n步。
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 ⊆ Rn 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.