{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:47:27Z","timestamp":1787507247338,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"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":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374379","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T12:50:20Z","timestamp":1211979020000},"page":"11-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling"],"prefix":"10.1145","author":[{"given":"Rajsekar","family":"Manokaran","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1079","volume-title":"SODA '04: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Archer Aaron","year":"2004","unstructured":"Aaron Archer , Jittat Fakcharoenphol , Chris Harrelson , Robert Krauthgamer , Kunal Talwar , and \u00c9va Tardos . Approximate classification via earthmover metrics . In SODA '04: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1079 -- 1087 , 2004 . Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and \u00c9va Tardos. Approximate classification via earthmover metrics. In SODA '04: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1079--1087, 2004."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334204"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_5_1","first-page":"8","volume-title":"SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Calinescu Gruia","year":"2001","unstructured":"Gruia Calinescu , Howard Karloff , and Yuval Rabani . Approximation algorithms for the 0-extension problem . In SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 8 -- 16 , 2001 . Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 8--16, 2001."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/06065430X"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276711"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129736"},{"key":"e_1_3_2_1_10_1","first-page":"257","volume-title":"SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Fakcharoenphol Jittat","year":"2003","unstructured":"Jittat Fakcharoenphol , Chris Harrelson , Satish Rao , and Kunal Talwar . An improved approximation algorithm for the 0-extension problem . In SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 257 -- 265 , 2003 . Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 257--265, 2003."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/992287.992300"},{"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.1145\/301250.301430"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132595"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050040"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.67"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.41"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","location":"Victoria British Columbia Canada","acronym":"STOC '08","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:22:32Z","timestamp":1750263752000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":26,"alternative-id":["10.1145\/1374376.1374379","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374379","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}