{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:16:31Z","timestamp":1787498191183,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2004,6,13]],"date-time":"2004-06-13T00:00:00Z","timestamp":1087084800000},"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":[[2004,6,13]]},"DOI":"10.1145\/1007352.1007363","type":"proceedings-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T11:55:38Z","timestamp":1090324538000},"page":"21-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Asymmetric k-center is log\n                    <sup>*<\/sup>\n                    <i>n<\/i>\n                    -hard to approximate"],"prefix":"10.1145","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Halperi","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Nao","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2004,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Approximation Algorithms for NP Hard Problems","author":"Arora S.","year":"1996","unstructured":"S. Arora and C. Lund . Hardness of approximation . In Dorit Hochbaum, editor, Approximation Algorithms for NP Hard Problems . PWS publishing Co , 1996 .]] S. Arora and C. Lund. Hardness of approximation. In Dorit Hochbaum, editor, Approximation Algorithms for NP Hard Problems. PWS publishing Co, 1996.]]"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645590.659930"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the ACM-SIAM symposium on Discrete Algorithms","author":"Charikar M.","year":"2001","unstructured":"M. Charikar , S. Khuller , D. M. Mount , and G. Narasimhan . Algorithms for facility location problems with outliers . Proceedings of the ACM-SIAM symposium on Discrete Algorithms 2001 .]] M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility location problems with outliers. Proceedings of the ACM-SIAM symposium on Discrete Algorithms 2001.]]"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90002-1"},{"key":"e_1_3_2_1_7_1","volume-title":"Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-\u03b5). Electronic Colloquium on Computational Complexity (ECCC), (027)","author":"Dinur I.","year":"2002","unstructured":"I. Dinur , V. Guruswami , and S. Khot . Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-\u03b5). Electronic Colloquium on Computational Complexity (ECCC), (027) , 2002 .]] I. Dinur, V. Guruswami, and S. Khot. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-\u03b5). Electronic Colloquium on Computational Complexity (ECCC), (027), 2002.]]"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780629"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652126"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509915"},{"key":"e_1_3_2_1_11_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-completeness . W. H. Freeman and Company , 1979 .]] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.]]"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 14th SIAM Symposium on Discrete Algorithms","author":"Halperin E.","year":"2003","unstructured":"E. Halperin , G. Kortsarz , R. Krauthgamer , A. Srinivasan , and N. Wang . Integrality ratio for group steiner trees and directed steiner trees . Proceedings of the 14th SIAM Symposium on Discrete Algorithms , 2003 .]] E. Halperin, G. Kortsarz, R. Krauthgamer, A. Srinivasan, and N. Wang. Integrality ratio for group steiner trees and directed steiner trees. Proceedings of the 14th SIAM Symposium on Discrete Algorithms, 2003.]]"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90044-1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509986"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"issue":"6","key":"e_1_3_2_1_18_1","first-page":"445","article-title":"On the computational complexity of centers locating in a graph","volume":"25","author":"Plesnik J.","year":"1980","unstructured":"J. Plesnik . On the computational complexity of centers locating in a graph . Aplikace Matematiky , 25 ( 6 ): 445 -- 452 , 1980 .]] J. Plesnik. On the computational complexity of centers locating in a graph. Aplikace Matematiky, 25(6):445--452, 1980.]]","journal-title":"Aplikace Matematiky"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0921"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/020\/07"},{"key":"e_1_3_2_1_22_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","year":"2001","unstructured":"V. V. Vazirani . Approximation Algorithms . Springer Verlag , 2001 .]] V. V. Vazirani. Approximation Algorithms. Springer Verlag, 2001.]]"}],"event":{"name":"STOC04: Symposium of Theory of Computing 2004","location":"Chicago IL USA","acronym":"STOC04","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007363","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1007352.1007363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:23:55Z","timestamp":1750253035000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,13]]},"references-count":22,"alternative-id":["10.1145\/1007352.1007363","10.1145\/1007352"],"URL":"https:\/\/doi.org\/10.1145\/1007352.1007363","relation":{},"subject":[],"published":{"date-parts":[[2004,6,13]]},"assertion":[{"value":"2004-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}