Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Aranyak Mehta:

TR05-064 | 26th June 2005
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

On earthmover distance, metric labeling, and 0-extension

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, ... more >>>

ISSN 1433-8092 | Imprint