Sherali-adams relaxations of the matching polytope
Sherali-adams relaxations of the matching polytope
复制标题
匹配多面体的 Sherali-adams 松弛
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Sinclair
中科院分区：
文献类型：
--
作者：
Claire Mathieu;A. Sinclair
我们研究了匹配多面体的线性规划松弛的 Sherali-Adams 提升和投影层次结构。我们的主要结果是该层次结构的 k 轮之后的完整性差距的渐近紧表达式 1+1/k。结果是通过对应用于完整图 K_{2d+1} 的 k 轮后的 LP 进行详细分析得出的。我们给出了该 LP 值的显式递推，因此表明其间隙表现出“相变”，从接近其最大值 1+1/2d 下降到接近阈值 k=2d-θ(√d) 附近的 1。我们还表明，匹配多胞形的等级（即，达到整数多胞形之前的 Sherali-Adams 轮数）恰好为 2d-1。
We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1+1/k for the integrality gap after k rounds of this hierarchy. The result is derived by a detailed analysis of the LP after k rounds applied to the complete graph K_{2d+1}. We give an explicit recurrence for the value of this LP, and hence show that its gap exhibits a "phase transition," dropping from close to its maximum value 1+1/2d to close to 1 around the threshold k=2d-Θ(√d). We also show that the rank of the matching polytope (i.e., the number of Sherali-Adams rounds until the integer polytope is reached) is exactly 2d-1.