Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-064 | 26th June 2005 00:00

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

TR05-064
Authors: Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
Publication: 26th June 2005 13:42
Keywords:

Abstract:

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
\begin{enumerate}
\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.
\end{enumerate}

ISSN 1433-8092 | Imprint