{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:21:03Z","timestamp":1778494863414,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540679967","type":"print"},{"value":"9783540444367","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_4","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T09:33:14Z","timestamp":1182159194000},"page":"27-32","source":"Crossref","is-referenced-by-count":74,"title":["Approximation Algorithms for Facility Location Problems"],"prefix":"10.1007","author":[{"given":"David B.","family":"Shmoys","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, P. Raghavan, and S. Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 106\u2013113, 1998.","DOI":"10.1145\/276698.276718"},{"key":"4_CR2","unstructured":"M. L. Balinksi. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pages 225\u2013248. IBM, 1966."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha. Improved combinatorial algorithms for the facility loca-tion and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 378\u2013388, 1999.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"M. Charikar, S. Guha, \u00c9. Tardos, and D. B. Shmoys. A constant-factor approximation algorithms for the k-median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 1\u201310, 1999.","DOI":"10.1145\/301250.301257"},{"key":"4_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/3-540-69346-7_14","volume-title":"Integer Programming and Combinatorial Optimization","author":"F. A. Chudak","year":"1998","unstructured":"F. A. Chudak. Improved approximation algorithms for uncapacitated facility location. In R.E. Bixby, E.A. Boyd, and R.Z. R\u00edos-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 180\u2013194, Berlin, 1998. Springer."},{"key":"4_CR6","unstructured":"F. A. Chudak and D. B Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Submitted for publication."},{"key":"4_CR7","unstructured":"S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 649\u2013657, 1998."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum. Heuristics for the fixed cost median problem. Math.Programming, 22:148\u2013162, 1982.","journal-title":"Math.Programming"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 2\u201313, 1999.","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"4_CR10","unstructured":"M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local searchheuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1\u201310, 1998."},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"A. A. Kuehn","year":"1963","unstructured":"A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses.Management Sci., 9:643\u2013666, 1963.","journal-title":"Management Sci."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"J.-H. Lin and J. S. Vitter. \u2208-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771\u2013782, 1992.","DOI":"10.1145\/129712.129787"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J.-H. Lin","year":"1992","unstructured":"J.-H. Lin and J. S. Vitter. Approximation algorithms for geometric median problems.Inform.Proc.Lett., 44:245\u2013249, 1992.","journal-title":"Inform.Proc.Lett."},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"A. S. Manne","year":"1964","unstructured":"A. S. Manne. Plant location under economies-of-scale-decentralization and computation.Management Sci., 11:213\u2013235, 1964.","journal-title":"Management Sci."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"R. R. Mettu and C. G. Plaxton. The online median problem. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, to appear.","DOI":"10.1109\/SFCS.2000.892122"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. I. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265\u2013274, 1997.","DOI":"10.1145\/258533.258600"},{"key":"4_CR18","volume-title":"The effect of tec nical change and output expansion on the optimum number,size and location of pear marketing facilities in a California pear producing region","author":"J. F. Stollsteimer","year":"1961","unstructured":"J. F. Stollsteimer. The effect of tec nical change and output expansion on the optimum number,size and location of pear marketing facilities in a California pear producing region. PhD thesis, University of California at Berkeley, Berkeley, California, 1961."},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"631","DOI":"10.2307\/1235442","volume":"45","author":"J. F. Stollsteimer","year":"1963","unstructured":"J. F. Stollsteimer. A working model for plant numbers and locations. J.Farm Econom., 45:631\u2013645, 1963.","journal-title":"J.Farm Econom."},{"key":"4_CR20","unstructured":"M. Thorup. Quick k-medians. Unpublished manuscript, 2000."}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:32:16Z","timestamp":1737102736000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}