{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:48Z","timestamp":1750307988515,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132595","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"547-556","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On earthmover distance, metric labeling, and 0-extension"],"prefix":"10.1145","author":[{"given":"Howard","family":"Karloff","sequence":"first","affiliation":[{"name":"AT&T Labs-Research, Florham Park, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[{"name":"Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"volume-title":"Proc. SODA '04","author":"Archer A.","key":"e_1_3_2_1_1_1","unstructured":"A. Archer , J. Fakcharoenphol , C. Harrelson , R. Krauthgamer , K. Talwar , and \u00c9. Tardos, Approximate classification via earthmover metrics , in Proc. SODA '04 . A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and \u00c9. Tardos, Approximate classification via earthmover metrics, in Proc. SODA '04."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02766125"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"e_1_3_2_1_7_1","volume-title":"private communication","author":"Charikar M.","year":"2000","unstructured":"M. Charikar , private communication , 2000 . M. Charikar, private communication, 2000."},{"key":"e_1_3_2_1_8_1","unstructured":"C. Chekuri S. Khanna J. Naor and L. Zosin Approximation algorithms for the Metric Labeling problem via a new linear programming formulation to appear in SIAM J. on Discrete Math (preliminary version in SODA '01).   C. Chekuri S. Khanna J. Naor and L. Zosin Approximation algorithms for the Metric Labeling problem via a new linear programming formulation to appear in SIAM J. on Discrete Math (preliminary version in SODA '01)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.67"},{"volume-title":"Proc. SODA '03","author":"Fakcharoenphol J.","key":"e_1_3_2_1_10_1","unstructured":"J. Fakcharoenphol , C. Harrelson , S. Rao , and K. Talwar , An improved approximation algorithm for the 0-Extension Problem , in Proc. SODA '03 , 342--352. J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar, An improved approximation algorithm for the 0-Extension Problem, in Proc. SODA '03, 342--352."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335397"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764938"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.54"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1994.365733"}],"event":{"name":"STOC06: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Seattle WA USA","acronym":"STOC06"},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132595","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":19,"alternative-id":["10.1145\/1132516.1132595","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132595","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}