Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling
复制标题
用于多向切割、0 延伸和公制标签的 Sdp 间隙和 ugc 硬度
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Roy Schwartz
中科院分区：
文献类型：
--
作者：
R. Manokaran;Joseph Naor;Prasad Raghavendra;Roy Schwartz
完整性差距与离散优化问题的计算硬度之间的联系是一个有趣的问题。近年来，这种联系在几个基于UGC紧密的硬度结果中显着。我们在本文中展示了一种直接的方式，将整数差距转化为几个基本分类问题的硬度结果。具体而言，我们将线性编程的完整性差距转换为多路切割，0扩展和度量标记问题的线性编程差距，并将其转换为基于UGC的硬度结果。从定性上讲，我们的结果表明，如果独特的游戏猜想是正确的，那么在几篇论文（所谓的地球线性计划）中研究的后一种问题的线性放松就会产生最好的近似值。进一步迈出一步，我们还获得了半定义编程放松与EarthMover线性程序的完整性差距相匹配的完整差距。在这项工作之前，有一种有趣的可能性，可以通过半定义编程获得更好的标记问题的近似因素。
The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGC-based hardness results. We show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. Specifically, we convert linear programming integrality gaps for the Multiway Cut, 0-Extension, and and Metric Labeling problems into UGC-based hardness results. Qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthmover linear program) yields the best possible approximation. Taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthmover linear program. Prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming.