{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:38:12Z","timestamp":1775083092407,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,5,18]],"date-time":"2010-05-18T00:00:00Z","timestamp":1274140800000},"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":[[2012,2]]},"DOI":"10.1007\/s10107-010-0380-8","type":"journal-article","created":{"date-parts":[[2010,5,17]],"date-time":"2010-05-17T07:44:16Z","timestamp":1274082256000},"page":"365-379","source":"Crossref","is-referenced-by-count":48,"title":["LP-based approximation algorithms for capacitated facility location"],"prefix":"10.1007","volume":"131","author":[{"given":"Retsef","family":"Levi","sequence":"first","affiliation":[]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,5,18]]},"reference":[{"key":"380_CR1","first-page":"149","volume":"81","author":"K. Aardal","year":"1998","unstructured":"Aardal K.: Capacitated facility location: separation algorithms and computational experience. Math. Programming 81, 149\u2013175 (1998)","journal-title":"Math. Programming"},{"key":"380_CR2","doi-asserted-by":"crossref","unstructured":"Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization, pp. 288\u2013302 (2008)","DOI":"10.1007\/978-3-540-68891-4_20"},{"key":"380_CR3","unstructured":"Carr, R., Fleischer, L., Leung, V., Phillips, C.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 106\u2013115 (2000)"},{"key":"380_CR4","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"F.A. Chudak","year":"2005","unstructured":"Chudak F.A., Williamson D.P.: Improved approximation algorithms for capacitated facility location problems. Math Programming 102, 207\u2013222 (2005)","journal-title":"Math Programming"},{"key":"380_CR5","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain K., Vazirani V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48, 274\u2013296 (2001)","journal-title":"J ACM"},{"issue":"1","key":"380_CR6","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M.R. Korupolu","year":"2000","unstructured":"Korupolu M.R., Plaxton C.G., Rajaraman R.: Analysis of a local search heuristic for facility location problems. J Algorithms 37(1), 146\u2013188 (2000)","journal-title":"J Algorithms"},{"key":"380_CR7","doi-asserted-by":"crossref","unstructured":"Levi, R., Lodi, A., Sviridenko, M.: Approximation algorithms for the multi-item capacitated lot-sizing problem via flow-cover inequalities. Mathematics of Operations Research 33, 461\u2013474 (2008) Preliminary version appeared in Proceedings of the 12th Conference on Integer Programming and Combinatorial Optimization, pp. 454\u2013468 (2007)","DOI":"10.1287\/moor.1070.0305"},{"key":"380_CR8","doi-asserted-by":"crossref","unstructured":"Levi, R., Shmoys, D., Swamy, C.: LP-based approximation algorithms for capacitated facility location. In: Proceedings of the 10th IPCO, pp. 206\u2013218 (2004)","DOI":"10.1007\/978-3-540-25960-2_16"},{"key":"380_CR9","doi-asserted-by":"crossref","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Proceedings of the 11th ESA, pp. 409\u2013421 (2003)","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"380_CR10","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M. Mahdian","year":"2006","unstructured":"Mahdian M., Ye Y., Zhang J.: Approximation algorithms for metric facility location problems. SIAM J. Computing 36, 411\u2013432 (2006)","journal-title":"SIAM J. Computing"},{"key":"380_CR11","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1287\/opre.33.4.842","volume":"33","author":"M.W. Padberg","year":"1985","unstructured":"Padberg M.W., Van Roy T.J., Wolsey L.A.: Valid linear inequalities for fixed charge problems. Operations Res. 33, 842\u2013861 (1985)","journal-title":"Operations Res."},{"key":"380_CR12","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"380_CR13","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B.: Approximation algorithms for facility location problems. In: Proceedings of 3rd APPROX, pp. 27\u201333 (2000)","DOI":"10.1007\/3-540-44436-X_4"},{"key":"380_CR14","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D.B. Shmoys","year":"1993","unstructured":"Shmoys D.B., Tardos \u00c9.: An approximation algorithm for the generalized assignment problem. Math Programming A 62, 461\u2013474 (1993)","journal-title":"Math Programming A"},{"key":"380_CR15","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"380_CR16","doi-asserted-by":"crossref","unstructured":"Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. ACM Transactions on Algorithms 4:4. Preliminary version appeared in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 735\u2013736 (2003)","DOI":"10.1145\/1383369.1383382"},{"key":"380_CR17","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J. Zhang","year":"2005","unstructured":"Zhang J., Chen B., Ye Y.: A multi-exchange local search algorithm for the capacitated facility location problem. Math. Operations Res. 30, 389\u2013403 (2005)","journal-title":"Math. Operations Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0380-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-010-0380-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0380-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:08Z","timestamp":1559123408000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-010-0380-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,18]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["380"],"URL":"https:\/\/doi.org\/10.1007\/s10107-010-0380-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,18]]}}}