{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:17:02Z","timestamp":1752229022148,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_21","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"249-260","source":"Crossref","is-referenced-by-count":24,"title":["Quick k-Median, k-Center, and Facility Location for Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Mikkel","family":"Thorup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. A constant-factor approximation algorithm for the k-median problem. In Proc. 31th STOC, pages 1\u201310, 1999.","DOI":"10.1145\/301250.301257"},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"E. Cohen. Size-estimation framework with applications to transitive closure and reachability. J. Comput. System Sci., 55(3):441\u2013453, 1997.","journal-title":"J. Comput. System Sci."},{"key":"21_CR3","unstructured":"E. Cohen and U. Zwick. All-pairs small-stretch paths. In Proc. 8th SODA, pages 93\u2013102, 1999."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596\u2013615, 1987.","journal-title":"J. ACM"},{"key":"21_CR5","unstructured":"A. Goel, P. Indyk, and K. Varadarajan. Reductions among high demensional proximity problems. In Proc. 10th SODA, pages 769\u2013778, 2001."},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. F. Gonzales","year":"1985","unstructured":"T. F. Gonzales. Clustering to minimize the maximum intercluster distance. Theor. Comp. Sci., 38:293\u2013550, 1985.","journal-title":"Theor. Comp. Sci."},{"key":"21_CR7","unstructured":"S. Guha, M. Mishra, R. Motwani, and L O\u2019Callaghan. Clustering data streams. In Proc. 41th FOCS, pages 359\u2013366, 2000."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D. Hochbaum","year":"1986","unstructured":"D. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33:533\u2013550, 1986.","journal-title":"J. ACM"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W.L. Hsu","year":"1979","unstructured":"W.L. Hsu and G.L. Nemhauser. Easy and hard bottleneck problems. Discr. Appl. Math., 1:209\u2013216, 1979.","journal-title":"Discr. Appl. Math."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"P. Indyk. Sublinear time algorithms for metric space problems. In Proc. 31th STOC, pages 428\u2013434, 1999.","DOI":"10.1145\/301250.301366"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the course of dimensionality. In Proc. 30th STOC, pages 604\u2013613, 1998.","DOI":"10.1145\/276698.276876"},{"key":"21_CR12","unstructured":"P. Indyk and M. Thorup. Approximate 1-medians, 2000."},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"K. Jain and V.V. Vazirani. Primal-dual approximation algorihtms for metric faciity location and k-median problems. In Proc. 40th FOCS, pages 2\u201313, 1999. The running times involve a certain factor L that will be removed in the journal version to appear in J. ACM.","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A simple parallel algorithm for the maiximal independent set. SIAM J. Comput., 15:1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"R.R. Mettu and C. G. Plaxton. The online medan problem. In Proc. 41th FOCS, pages 339\u2013348, 2000.","DOI":"10.1109\/SFCS.2000.892122"},{"issue":"4","key":"21_CR16","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1287\/mnsc.29.4.482","volume":"29","author":"B.C. Tansel","year":"1983","unstructured":"B.C. Tansel, R.L. Francis, and T.J. Lowe. Location on networks: A survey. part 1 and 2. Management Science, 29(4):482\u2013511, 1983.","journal-title":"Management Science"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"M. Thorup. Undirected single source shortest paths with positive integer weights in linear time. J. ACM, 46:362\u2013394, 1999.","journal-title":"J. ACM"},{"issue":"1","key":"21_CR18","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S0097539795288246","volume":"30","author":"M. Thorup","year":"2000","unstructured":"M. Thorup. On RAM priority queues. SIAM J. Comput., 30(1):86\u2013109, 2000.","journal-title":"SIAM J. Comput."},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick. Approximate distance oracles, 2000. Accepted for STOC\u201901.","DOI":"10.1145\/380752.380798"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:09Z","timestamp":1737503409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}