Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-064 | 26th June 2005 00:00

On earthmover distance, metric labeling, and 0-extension


Authors: Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
Publication: 26th June 2005 13:42
Downloads: 3666


We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, for either {\sc Metric Labeling} or {\sc 0-Extension}. We prove
\item that the integrality ratio of the earthmover relaxation for {\sc Metric Labeling} is $\Omega(\log k)$, $k$ being the number of labels (this bound is tight), whereas the best previous lower bound on the integrality ratio was constant;
\item that the integrality ratio of the earthmover relaxation for {\sc 0-Extension} is $\Omega(\sqrt{\log k})$, $k$ being the number of terminals (the integrality ratio was known to be $O((\log k)/\log\log k)$), whereas the best previous lower bound was constant;
\item that for no $\epsilon>0$ is there a polynomial-time $O((\log n)^{1/4-\eps})$-approximation algorithm for {\sc 0-Extension}, $n$ being the number of vertices, unless NP$\subseteq$DTIME$(n^{\poly(\log n)})$, whereas the strongest inapproximability result known before was MAX SNP-hardness; and
\item that there is a polynomial-time approximation algorithm for {\sc 0-Extension} with performance ratio $O(\sqrt{\diam(d)})$, where $\diam(d)$ is the ratio of largest distance to smallest nonzero distance in the terminal metric.

ISSN 1433-8092 | Imprint