{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:40Z","timestamp":1787340400129,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We study the fundamental classification problems 0-Extension and Metric Labeling. A generalization of Multiway Cut, 0-Extension is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization Metric Labeling is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial\u2013time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant. We prove (1) that the integrality ratio of the earthmover relaxation for Metric Labeling is $\\Omega(\\log k)$ (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; (2) that the integrality ratio of the earthmover relaxation for 0-Extension is $\\Omega(\\sqrt{\\log k})$, k being the number of terminals (it was known to be $O((\\log k)\/\\log\\log k)$), whereas the best previous lower bound was only constant; (3) that for no $\\epsilon&gt;0$ is there a polynomial-time $O((\\log n)^{1\/4-\\epsilon})$-approximation algorithm for 0-Extension, n being the number of vertices, unless NP$\\subseteq$DTIME$(n^{\\mathrm{poly}(\\log n)})$, whereas the strongest inapproximability result known before was only MAX SNP-hardness; and (4) that there is a polynomial-time approximation algorithm for 0-Extension with performance ratio $O(\\sqrt{\\mathrm{diam}(d)})$, where $\\mathrm{diam}(d)$ is the ratio of the largest to smallest nonzero distances in the terminal metric.<\/jats:p>","DOI":"10.1137\/070685671","type":"journal-article","created":{"date-parts":[[2009,6,3]],"date-time":"2009-06-03T18:07:36Z","timestamp":1244052456000},"page":"371-387","source":"Crossref","is-referenced-by-count":8,"title":["On Earthmover Distance, Metric Labeling, and 0-Extension"],"prefix":"10.1137","volume":"39","author":[{"given":"Howard","family":"Karloff","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,6,3]]},"reference":[{"key":"R1","unstructured":"A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and \u00c9. Tardos,\n                      Approximate classification via earthmover metrics\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp. 1072\u20131080."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 1998, pp. 448\u2013455.","DOI":"10.1145\/276698.276725"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02766125"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"R6","unstructured":"M. Charikar,\n                      private communication\n                      , 2000."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/06065430X"},{"key":"R9","unstructured":"J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar,\n                      An improved approximation algorithm for the 0-extension problem\n                      , in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 257\u2013265."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Gupta and E. Tardos,\n                      A constant factor approximation algorithm for a class of classification problems\n                      , in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), 2000, pp. 652\u2013658.","DOI":"10.1145\/335305.335397"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764938"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-005-0745-0"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070685671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:21Z","timestamp":1787337201000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070685671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070685671"],"URL":"https:\/\/doi.org\/10.1137\/070685671","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}