{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T12:47:58Z","timestamp":1772714878787,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"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":["J. ACM"],"published-print":{"date-parts":[[2005,7]]},"abstract":"\n In the ASYMMETRIC\n k<\/jats:italic>\n -CENTER problem, the input is an integer\n k<\/jats:italic>\n and a complete digraph over\n n<\/jats:italic>\n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of\n k<\/jats:italic>\n points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point from its center is as small as possible.We show that the ASYMMETRIC\n k<\/jats:italic>\n -CENTER problem is hard to approximate up to a factor of log\n *<\/jats:sup>\n n<\/jats:italic>\n \u2212\n O<\/jats:italic>\n (1) unless\n NP<\/jats:bold>\n \u2286\n DTIME<\/jats:bold>\n (\n n<\/jats:italic>\n log log<\/jats:sup>\n n<\/jats:italic>\n ). Since an\n O<\/jats:italic>\n (log\n *<\/jats:sup>\n n<\/jats:italic>\n )-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC\n k<\/jats:italic>\n -CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric)\n k<\/jats:italic>\n -Center problem with costs.\n <\/jats:p>","DOI":"10.1145\/1082036.1082038","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"538-551","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Asymmetric\n k<\/i>\n -center is log\n *<\/sup>\n n<\/i>\n -hard to approximate"],"prefix":"10.1145","volume":"52","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"MIT, Cambridge Massachusetts"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, Pennsylvania, Philadelphia, PA"}]},{"given":"Eran","family":"Halperin","sequence":"additional","affiliation":[{"name":"International Computer Science Institute, Berkeley, California, and University of California, Berkeley, Berkeley, California, CA"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, Pennsylvania, Philadelphia, PA"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, New Jersey"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[{"name":"International Computer Science Institute, Berkeley, California, and University of California, Berkeley, Berkeley, California, CA"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","volume-title":"Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization","author":"Archer A. F."},{"key":"e_1_2_1_2_1","volume-title":"Approximation Algorithms for NP Hard Problems, Dorit Hochbaum, Ed","author":"Arora S."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_5_1","first-page":"642","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Charikar M."},{"key":"e_1_2_1_6_1","unstructured":"Dinur I. Guruswami V. and Khot S.2002b. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k−3−ε). Electronic Colloquium on Computational Complexity (ECCC) (027).]] Dinur I. Guruswami V. and Khot S.2002b. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k−3−ε). Electronic Colloquium on Computational Complexity (ECCC) (027).]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780629"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 43rd IEEE Symposium on","author":"Dinur I."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509915"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90002-1"},{"key":"e_1_2_1_11_1","volume-title":"1979. Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey M. R."},{"key":"e_1_2_1_12_1","unstructured":"Goldreich O.2001. Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. Electronic Colloquium on Computational Complexity (ECCC) 102.]] Goldreich O.2001. Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. Electronic Colloquium on Computational Complexity (ECCC) 102.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_14_1","first-page":"275","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Halperin E."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509986"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90044-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0921"},{"key":"e_1_2_1_20_1","first-page":"445","article-title":"On the computational complexity of centers locating in a graph","volume":"25","author":"Plesn\u00edk J.","year":"1980","journal-title":"Aplik. Matem."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_22_1","first-page":"355","volume-title":"Eds. AMS","author":"Shmoys D. B."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","DOI":"10.1007\/978-3-662-04565-7"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1082036.1082038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:46Z","timestamp":1750263526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1082036.1082038"],"URL":"https:\/\/doi.org\/10.1145\/1082036.1082038","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}