On earthmover distance, metric labeling, and 0-extension

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages547-556
Number of pages10
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/23/06

Keywords

  • Algorithms
  • Theory

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On earthmover distance, metric labeling, and 0-extension'. Together they form a unique fingerprint.

Cite this