{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T07:37:51Z","timestamp":1773733071093,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2004,5,31]],"date-time":"2004-05-31T00:00:00Z","timestamp":1085961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2005,3]]},"DOI":"10.1007\/s10107-004-0524-9","type":"journal-article","created":{"date-parts":[[2004,5,29]],"date-time":"2004-05-29T07:59:29Z","timestamp":1085817569000},"page":"207-222","source":"Crossref","is-referenced-by-count":63,"title":["Improved approximation algorithms for capacitated facility location problems"],"prefix":"10.1007","volume":"102","author":[{"given":"Fabi\ufffdn A.","family":"Chudak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2004,5,31]]},"reference":[{"key":"CR1","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. In: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 485?495","DOI":"10.1145\/258533.258642"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01585522","volume":"7","author":"Babayev","year":"1974","unstructured":"Babayev, Dj.A.: Comments on the note of Frieze. Math. Program. 7, 249?252 (1974)","journal-title":"Math. Program."},{"key":"CR4","first-page":"101","volume":"83","author":"Barahona","year":"1998","unstructured":"Barahona, F., Jensen, D.: Plant location with minimum inventory. Math. Program. 83, 101?111 (1998)","journal-title":"Math. Program."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science, 1999, pp. 378?388","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Chudak, F.: Improved approximation algorithms for uncapacitated facility location. In: Proceedings of the 6th IPCO Conference, 1998, pp. 180?194","DOI":"10.1007\/3-540-69346-7_14"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"Chudak","year":"2003","unstructured":"Chudak, F., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1?25 (2003)","journal-title":"SIAM J. Comput."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Chudak, F., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 875?876","DOI":"10.1007\/3-540-48777-8_8"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Chudak, F., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th IPCO Conference, 1999, pp. 99?113","DOI":"10.1007\/3-540-48777-8_8"},{"key":"CR10","unstructured":"Cornu\u00e9jols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. In: P. Mirchandani and R. Francis, (eds.), Discrete Location Theory, John Wiley and Sons, Inc., New York, 1990, pp. 119?171"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"Feige","year":"1998","unstructured":"Feige, U.: A threshold of n for approximating set-cover. J. ACM 45, 634?652 (1998)","journal-title":"J. ACM"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 228?248 (1999)","journal-title":"J. Algorithms"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"Korupolu","year":"2000","unstructured":"Korupolu, M., Plaxton, C., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 146?188 (2000)","journal-title":"J. Algorithms"},{"key":"CR14","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960?981 (1994)","journal-title":"J. ACM"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2002, pp. 229?242","DOI":"10.1007\/3-540-45753-4_20"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2003, pp. 129?140","DOI":"10.1007\/978-3-540-45198-3_12"},{"key":"CR18","unstructured":"Mirchandani, P., Francis, R., eds.: Discrete Location Theory. John Wiley and Sons, Inc., New York, 1990"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions ? I. Math. Program. 14, 265?294 (1978)","journal-title":"Math. Program."},{"key":"CR20","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 41st IEEE Symposium on the Foundations of Computing, 2001, pp. 329?338"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: 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, 1997, pp. 475?484","DOI":"10.1145\/258533.258641"},{"key":"CR22","unstructured":"Shmoys, D., Tardos, \u00c9, Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 265?274"},{"key":"CR23","unstructured":"Sviridenko, M.: Personal communication, July, 1998"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0524-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-004-0524-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0524-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:49:57Z","timestamp":1559123397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-004-0524-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,5,31]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["524"],"URL":"https:\/\/doi.org\/10.1007\/s10107-004-0524-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,5,31]]}}}