On earthmover distance, metric labeling, and 0-extension
On earthmover distance, metric labeling, and 0-extension
复制标题
关于推土机距离、公制标签和 0 延伸
DOI：
10.1145/1132516.1132595
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Y. Rabani
中科院分区：
文献类型：
--
作者：
H. Karloff;Subhash Khot;Aranyak Mehta;Y. Rabani
我们研究基本的分类问题O-扩张和度量标注。最小权三角剖分与图论中的划分问题和Banach空间中的Lipschitz扩张密切相关;它的推广度量标号是由计算机视觉中的应用所激发的。研究人员曾提议使用推土机度量来获得这些问题的多项式时间可解松弛。最近引起人们注意的一个猜想是这些弛豫的完整性比是常数，我们证明了度量标记的推土机弛豫的完整性比是Ω（logn）（这是渐近紧的），k是标签的数量，而完整性比的最佳先前下限仅为常数; O-EXTENSION的推土机松弛的完整性比为Ω（Ω log k），k为终端数（已知它是O（（log k）/log log k）），而最好的前一个下界只是常数;如果没有ε>0，是否存在O-扩张的多项式时间O（（log n）1/4-ε）-近似算法，n是顶点数，除非NP ≠ DTIME（npoly（log n）），而之前已知的最强不可近似性结果仅为MAX SNP-硬度;并且存在性能比为O（λ diam（d））的O-EXTENSION的多项式时间近似算法，其中diam（d）是终端度量中最大与最小非零距离的比率。
We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove that the integrality ratio of the earthmover relaxation for METRIC LABELING is Ω(log n) (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; that the integrality ratio of the earthmover relaxation for O-EXTENSION is Ω(√log k), k being the number of terminals (it was known to be O((log k)/log log k)), whereas the best previous lower bound was only constant; that for no ε>0 is there a polynomial-time O((log n)1/4-ε)-approximation algorithm for O-EXTENSION, n being the number of vertices, unless NP ⊆ DTIME(npoly(log n)), whereas the strongest inapproximability result known before was only MAX SNP-hardness; and that there is a polynomial-time approximation algorithm for O-EXTENSION with performance ratio O(√diam(d)), where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.