{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:54:22Z","timestamp":1781078062315,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540660194","type":"print"},{"value":"9783540487777","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48777-8_8","type":"book-chapter","created":{"date-parts":[[2007,3,2]],"date-time":"2007-03-02T08:43:11Z","timestamp":1172824991000},"page":"99-113","source":"Crossref","is-referenced-by-count":71,"title":["Improved Approximation Algorithms for Capacitated Facility Location Problems"],"prefix":"10.1007","author":[{"given":"Fabi\u00e1n A.","family":"Chudak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1999,4,30]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora and M. Sudan. Improved low-degree testing and its applications. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 4850\u2013495, 1997.","DOI":"10.1145\/258533.258642"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01585522","volume":"7","author":"Dj. A. Babayev","year":"1974","unstructured":"Dj. A. Babayev. Comments on the note of Frieze. Mathematical Programming 7:249\u2013252, 1974.","journal-title":"Mathematical Programming"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0025-5610(97)00113-5","volume":"83","author":"F. Barahona","year":"1998","unstructured":"F. Barahona and D. Jensen. Plant location with minimum inventory. Mathematical Programming 83:101\u2013111, 1998.","journal-title":"Mathematical Programming"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"F. Chudak. Improved approximation algorithms for uncapacitated facility location. In Proceedings of the 6th IPCO Conference, pages 180\u2013194, 1998.","DOI":"10.1007\/3-540-69346-7_14"},{"key":"8_CR5","unstructured":"F. Chudak and D.B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. In preparation."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"F. Chudak and D.B. Shmoys. Improved approximation algorithms for a capacitated facility location problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 875\u2013876, 1999.","DOI":"10.1007\/3-540-48777-8_8"},{"key":"8_CR7","first-page":"119","volume-title":"Discrete Location Theory","author":"G. Cornu\u00e9jols","year":"1990","unstructured":"G. Cornu\u00e9jols, G. Nemhauser, and L. Wolsey. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119\u2013171. John Wiley and Sons, Inc., New York, 1990."},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"U. Feige. A threshold of ln n for approximating set-cover. In Proceedings of the 28th ACM Symposium on Theory of Computing, pages 314\u2013318, 1996.","DOI":"10.1145\/237814.237977"},{"key":"8_CR9","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":"8_CR10","unstructured":"M. Korupolu, C. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1\u201310, 1998."},{"key":"8_CR11","unstructured":"M. Korupolu, C. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Technical Report 98-30, DIMACS, June 1998. Available from http:\/\/dimacs.rutgers.edu\/TechnicalReports\/1998.html ."},{"key":"8_CR12","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976."},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. JACM 41:960\u2013981, 1994.","journal-title":"JACM"},{"key":"8_CR14","volume-title":"Discrete Location Theory","year":"1990","unstructured":"P. Mirchandani and R. Francis, eds. Discrete Location Theory. John Wiley and Sons, Inc., New York, 1990."},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. An analysis of approximations for maximizing submodular set functions \u2014 I. Mathematical Programming 14:265\u2013294, 1978.","journal-title":"Mathematical Programming"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 475\u2013484, 1997.","DOI":"10.1145\/258533.258641"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"D. Shmoys, \u00c9. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 265\u2013274, 1997.","DOI":"10.1145\/258533.258600"},{"key":"8_CR18","unstructured":"M. Sviridenko, July, 1998. Personal communication."}],"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-48777-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T22:18:40Z","timestamp":1556144320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48777-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540660194","9783540487777"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-48777-8_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}