TR05-064 Authors: Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

Publication: 26th June 2005 13:42

Downloads: 3637

Keywords:

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}