ECCC-Report TR05-064https://eccc.weizmann.ac.il/report/2005/064Comments and Revisions published for TR05-064en-usSun, 26 Jun 2005 13:42:02 +0300
Paper TR05-064
| On earthmover distance, metric labeling, and 0-extension |
Howard Karloff,
Subhash Khot,
Aranyak Mehta,
Yuval Rabani
https://eccc.weizmann.ac.il/report/2005/064We 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}
Sun, 26 Jun 2005 13:42:02 +0300https://eccc.weizmann.ac.il/report/2005/064