TY - GEN

T1 - On earthmover distance, metric labeling, and 0-extension

AU - Karloff, Howard

AU - Khot, Subhash

AU - Mehta, Aranyak

AU - Rabani, Yuval

PY - 2006

Y1 - 2006

N2 - We study the fundamental classification problems 0-EXTENSION and METRIC LABELING. 0-EXTENSION 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 1. 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; 2. that the integrality ratio of the earthmover relaxation for 0-ExTENSiON is Ω(√logk), 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; 3. that for no ε > 0 is there a polynomial-time O((log n)1/4-ε)-approximation algorithm for 0-EXTENSION, n being the number of vertices, unless NP⊆DTIME(npoly(log n)), whereas the strongest in-approximability result known before was only MAX SNP-hardness; and 4. that there is a polynomial-time approximation algorithm for 0-EXTENSION with performance ratio O(√diam((d)) where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.

AB - We study the fundamental classification problems 0-EXTENSION and METRIC LABELING. 0-EXTENSION 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 1. 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; 2. that the integrality ratio of the earthmover relaxation for 0-ExTENSiON is Ω(√logk), 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; 3. that for no ε > 0 is there a polynomial-time O((log n)1/4-ε)-approximation algorithm for 0-EXTENSION, n being the number of vertices, unless NP⊆DTIME(npoly(log n)), whereas the strongest in-approximability result known before was only MAX SNP-hardness; and 4. that there is a polynomial-time approximation algorithm for 0-EXTENSION with performance ratio O(√diam((d)) where diam(d) is the ratio of the largest to smallest nonzero distances in the terminal metric.

KW - Algorithms

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=33748120676&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748120676&partnerID=8YFLogxK

U2 - 10.1145/1132516.1132595

DO - 10.1145/1132516.1132595

M3 - Conference contribution

AN - SCOPUS:33748120676

SN - 1595931341

SN - 9781595931344

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 547

EP - 556

BT - STOC'06

PB - Association for Computing Machinery

T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06

Y2 - 21 May 2006 through 23 May 2006

ER -