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
复制标题
切割多面体半定层次结构中迭代次数的下界
DOI：
10.1287/moor.28.4.871.20508
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Laurent
中科院分区：
文献类型：
--
作者：
M. Laurent
Lasserre (2001a) 以及 LovAisz 和 Schrijver (1991) 构建了 0/1 多面体的半定松弛层次结构。 n 个节点上的图的切割多面体可以表示为最多 n 个步骤之后的这种半定松弛的投影。我们证明需要 [ n/2] 次迭代才能找到完整图 K n 的切割多胞形。
Hierarchies of semidefinite relaxations for 0/1 polytopes have been constructed by Lasserre (2001a) and by LovAisz and Schrijver (1991). The cut polytope of a graph onn nodes can be expressed as a projection of such a semidefinite relaxation after at mostn steps. We show that [ n/2] iterations are needed for finding the cut polytope of the complete graphK n .