Convex Relaxations and Integrality Gaps
Convex Relaxations and Integrality Gaps
复制标题
DOI：
10.1007/978-1-4614-0769-0_6
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
E. Chlamtác;Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
E. Chlamtác;Madhur Tulsiani
讨论了线性松弛和半定松弛逼近组合优化问题最优解的有效性。这些松弛的不同层次，例如Lovasz和Schrijver、Sherali和Adams以及Lasserre定义的松弛，从基本的松弛开始产生越来越强的线性和半定规划松弛。我们考察了这些层次的一些积极应用，在这些应用中，它们的使用产生了改进的近似算法。我们还讨论了由这些方程引起的松弛的完整性缺口的已知下界，证明了这些方程对某些优化问题的适用性的极限。
We discuss the effectiveness of linear and semidefinite relaxations in approximating the optimum for combinatorial optimization problems. Various hierarchies of these relaxations, such as the ones defined by Lovasz and Schrijver, Sherali and Adams, and Lasserre generate increasingly strong linear and semidefinite programming relaxations starting from a basic one. We survey some positive applications of these hierarchies, where their use yields improved approximation algorithms. We also discuss known lower bounds on the integrality gaps of relaxations arising from these hierarchies, demonstrating limits on the applicability of such hierarchies for certain optimization problems.