{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:16Z","timestamp":1774421296113,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422259","type":"print"},{"value":"9783540455356","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45535-3_1","type":"book-chapter","created":{"date-parts":[[2010,2,11]],"date-time":"2010-02-11T19:39:51Z","timestamp":1265917191000},"page":"1-14","source":"Crossref","is-referenced-by-count":18,"title":["Two O(log* k)-Approximation Algorithms for the Asymmetric k-Center Problem"],"prefix":"10.1007","author":[{"given":"Aaron","family":"Archer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,21]]},"reference":[{"key":"1_CR1","unstructured":"A. Archer, \u201cInapproximability of the asymmetric facility location and k-median problems,\u201d unpublished manuscript."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha, \u201cImprovedcom binatorial algorithms for the facility location and k-median problems,\u201d Proc. 40th Annual IEEE Symp. on Foundations of Computer Science, (1999) 378\u2013388.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"V. Chvatal, \u201cA greedy heuristic for the set covering problem,\u201d Math. Oper. Res., 4 (1979) 233\u2013235.","journal-title":"Math. Oper. Res."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0167-6377(85)90002-1","volume":"3","author":"M. Dyer","year":"1985","unstructured":"M. Dyer and A. Frieze, \u201cA simple heuristic for the p-centre problem,\u201d Oper. Res. Lett., 3 (1985) 285\u2013288.","journal-title":"Oper. Res. Lett."},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum, \u201cHeuristics for the fixedcost median problem,\u201d Math. Prog., 22 (1982) 148\u2013162.","journal-title":"Math. Prog."},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D. S. Hochbaum","year":"1985","unstructured":"D. S. Hochbaum and D. B. Shmoys, \u201cA best possible heuristic for the k-center problem,\u201d Math. Oper. Res. 10 (1985) 180\u2013184.","journal-title":"Math. Oper. Res."},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D. S. Hochbaum","year":"1986","unstructured":"D. S. Hochbaum and D. B. Shmoys, \u201cA unifiedapproac h to approximation algorithms for bottleneck problems,\u201d J. ACM, 33 (1986) 533\u2013550.","journal-title":"J. ACM"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, \u201cApproximation algorithms for combinatorial problems,\u201d J. Computer and System Sciences, 9 (1974) 256\u2013278.","journal-title":"J. Computer and System Sciences"},{"key":"1_CR9","unstructured":"J. Kleinberg, personal communication, November 1999."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"J.-H. Lin and J. S. Vitter, \u201c\u2208-approximations with minimum packing constraint violation\u201d, Proc. 24th Annual ACM Symp. on Theory of Computing, (1992) 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz, \u201cOn the ratio of optimal integral and fractional covers,\u201d Discrete Math., 13 (1975) 383\u2013390.","journal-title":"Discrete Math."},{"key":"1_CR12","unstructured":"R. O\u2019Donnell, personal communication, June 2000."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jagm.1997.0921","volume":"27","author":"R. Panigrahy","year":"1998","unstructured":"R. Panigrahy and S. Vishwanathan, \u201cAn O(log* n) approximation algorithm for the asymmetric p-center problem,\u201d J. Algorithms, 27 (1998) 259\u2013268.","journal-title":"J. Algorithms"},{"key":"1_CR14","unstructured":"S. Vishwanathan, \u201cAn O(log* n) approximation algorithm for the asymmetric p-center problem,\u201d Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms, (1996) 1\u20135."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45535-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T10:27:45Z","timestamp":1739874465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45535-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422259","9783540455356"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45535-3_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}