{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:24:55Z","timestamp":1787340295941,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set L of labels and a weighted graph $G=(V,E)$. Additionally, a metric distance function on the labels is defined, and for each label and each vertex, an assignment cost is given. The goal is to find a minimum\u2010cost assignment of the vertices to the labels. The cost of the solution consists of two parts: the assignment costs of the vertices and the separation costs of the edges (where each edge pays its weight times the distance between the two labels to which its endpoints are assigned). Due to the simple structure and the variety of applications, the problem and its special cases (with various distance functions on the labels) have recently received much attention. Metric labeling is known to have a logarithmic approximation, and it has been an open question for some time whether a constant approximation exists. We refute this possibility and prove that no constant factor approximation algorithm exists for metric labeling unless P=NP. Moreover, we prove that the problem is $\\Omega((\\log |V|)^{1\/2-\\delta})$\u2010hard to approximate for any constant $\\delta: 0&lt;\\delta&lt;1\/2$, unless NP has quasi\u2010polynomial time algorithms.<\/jats:p>","DOI":"10.1137\/06065430x","type":"journal-article","created":{"date-parts":[[2007,2,21]],"date-time":"2007-02-21T16:07:26Z","timestamp":1172074046000},"page":"1376-1386","source":"Crossref","is-referenced-by-count":12,"title":["The Hardness of Metric Labeling"],"prefix":"10.1137","volume":"36","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,1,12]]},"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 15th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, SIAM, Philadelphia, 2004, pp. 1072\u20131080."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximation of metric spaces and its algorithmic applications\n                      , in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, Burlington, VT, 1996, IEEE Press, Piscataway, NJ, 1996, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, ACM, New York, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"R10","unstructured":"J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar,\n                      An improved approximation algorithm for the 0\u2010extension problem\n                      , in Proceedings of the 14th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Baltimore, MD, 2003, SIAM, Philadelphia, 2003, pp. 257\u2013265."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,\n                      A tight bound on approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2003, ACM, New York, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R13","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 ACM Symposium on the Theory of Computing, Portland, OR, 2000, ACM, New York, 2000, pp. 652\u2013658.","DOI":"10.1145\/335305.335397"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"H. Karloff, S. Khot, A. Mehta, and Y. Rabani,\n                      On earthmover distance, metric labeling, and 0\u2010extension\n                      , in Proceedings of the 38th Annual ACM symposium on Theory of Computing, Seattle, WA, 2006, ACM, New York, 2006, pp. 547\u2013556.","DOI":"10.1145\/1132516.1132595"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050040"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/06065430X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:50Z","timestamp":1787336930000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/06065430X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/06065430X"],"URL":"https:\/\/doi.org\/10.1137\/06065430x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}