{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:38:10Z","timestamp":1775083090274,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540407706","type":"print"},{"value":"9783540451983","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_12","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"129-140","source":"Crossref","is-referenced-by-count":31,"title":["A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Mohammad","family":"Mahdian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiawei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: Proceedings of 33rd ACM Symposium on Theory of Computing (2001)","DOI":"10.1145\/380752.380755"},{"key":"12_CR2","unstructured":"Bauer, P., Enders, R.: A capacitated facility location problem with integer decision variables. In: International Symposium on Mathematical Programming, ISMP (1997)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378\u2013388 (October 1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","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":"Chudak, F.A.: Improved approximation algorithms for uncapacited facility location. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 180\u2013194. Springer, Heidelberg (1998)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem (1998) (unpublished manuscript)","DOI":"10.1007\/3-540-69346-7_14"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Shmoys, D.: Improved approximation algorithms for the capacitated facility location problem. In: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875\u2013876 (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"key":"12_CR7","first-page":"119","volume-title":"Discrete Location Theory","author":"G. Cornuejols","year":"1990","unstructured":"Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 119\u2013171. John Wiley and Sons Inc., Chichester (1990)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. Journal of Algorithms\u00a031, 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/net.10080","volume":"42","author":"M. Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Networks\u00a042(1), 42\u201347 (2003)","journal-title":"Networks"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0377-2217(94)90184-8","volume":"74","author":"K. Holmberg","year":"1994","unstructured":"Holmberg, K.: Solving the staircase cost facility location problem with decomposition and piecewise linearization. European Journal of Operational Research\u00a074, 41\u201361 (1994)","journal-title":"European Journal of Operational Research"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Approximation algorithms for facility location via dual fitting with factor-revealing LP. To appear in Journal of the ACM (2002)","DOI":"10.1145\/950620.950621"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34st Annual ACM Symposium on Theory of Computing (2002)","DOI":"10.1145\/509907.510012"},{"key":"12_CR13","doi-asserted-by":"publisher","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. Journal of the ACM\u00a048, 274\u2013296 (2001)","journal-title":"Journal of the ACM"},{"key":"12_CR14","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th Annual ACM SIAM Symposium on Discrete Algorithms, January 1998, pp. 1\u201310 (1998)"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/3-540-44666-4_16","volume-title":"Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques","author":"M. Mahdian","year":"2001","unstructured":"Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: A greedy facility location algorithm analyzed using dual fitting. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol.\u00a02129, pp. 127\u2013137. Springer, Heidelberg (2001)"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, p. 229. Springer, Heidelberg (2002)"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.B. Shmoys","year":"2000","unstructured":"Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 27\u201333. Springer, Heidelberg (2000)"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., 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":"12_CR19","doi-asserted-by":"crossref","unstructured":"Sviridenko, M.: An 1.582-approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/3-540-48224-5_21","volume-title":"Automata, Languages and Programming","author":"M. Thorup","year":"2001","unstructured":"Thorup, M.: Quick k-median, k-center, and facility location for sparse graphs. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 249\u2013260. Springer, Heidelberg (2001)"},{"key":"12_CR21","unstructured":"Thorup, M.: Quick and good facility location. In: Proceedings of the 14th ACMSIAM symposium on Discrete Algorithms (2003)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:18Z","timestamp":1559916318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}