{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:14:05Z","timestamp":1759335245215},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,5]],"date-time":"2015-06-05T00:00:00Z","timestamp":1433462400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0012-z","type":"journal-article","created":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T15:09:11Z","timestamp":1433430551000},"page":"53-83","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem"],"prefix":"10.1007","volume":"75","author":[{"given":"Babak","family":"Behsaz","sequence":"first","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Zoya","family":"Svitkina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,5]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Anand, L., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A 3-approximation for facility location with uniform capacities. In: Integer Programming and Combinatorial Optimization, vol 6080 of Lecture Notes in Computer Science, pp. 149\u2013162. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13036-6_12"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Alzoubi, H.A., Lee, S., Rabinovich, M., Spatscheck, O., der Merwe, J.: Anycast CDNS revisited. In: WWW \u201908: Proceeding of the 17th International Conference on World Wide Web, pp. 277\u2013286. ACM, New York, NY (2008)","DOI":"10.1145\/1367497.1367536"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 2\u201312. IEEE Computer Society, Washington, DC (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 554\u2013563. IEEE Computer Society, Washington, DC (1997)","DOI":"10.1109\/SFCS.1997.646145"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the Thirteeth Annual ACM Symposium on Theory of Computing, STOC \u201998, pp. 106\u2013113. ACM, New York, NY (1998)","DOI":"10.1145\/276698.276718"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., K., Rohit, M., Adam, M., Kamesh, P., Vinayaka: Local search heuristic for k-median and facility location problems. In: STOC \u201901: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 21\u201329. ACM, New York, NY (2001)","DOI":"10.1145\/380752.380755"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: 20th European Symposium on Algorithms, pp. 133\u2013144 (2012)","DOI":"10.1007\/978-3-642-33090-2_13"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC \u201998: Proceedings of the Thirteeth Annual ACM symposium on Theory of computing, pp. 161\u2013168. ACM, New York, NY (1998)","DOI":"10.1145\/276698.276725"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Bateni, M.H., Hajiaghayi, M.T.: Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805\u2013814 (2009)","DOI":"10.1137\/1.9781611973068.88"},{"key":"12_CR10","unstructured":"Behsaz, B.: Approximation Algorithms for Clustering Problems. PhD thesis, University of Alberta, Department of Computing Science (2012)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Byrka, J.: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In: APPROX \u201907\/RANDOM \u201907: Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 29\u201343. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, pp. 378\u2013388. IEEE Computer Society, Washington, DC (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Chudak, F.: Improved approximation algorithms for uncapacitated facility location. In: Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pp. 180\u2013194. Springer, Berlin (1998)","DOI":"10.1007\/3-540-69346-7_14"},{"key":"12_CR14","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: SODA \u201999: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875\u2013876. Society for Industrial and Applied Mathematics, Philadelphia, PA (1999)"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 99\u2013113. Springer, London (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"issue":"4","key":"12_CR16","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Vega de la","year":"1981","unstructured":"de la Vega, W., Lueker, G.S.: Bin packing can be solved within $$1+\\epsilon $$ 1 + \u03f5 in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"12_CR17","volume-title":"Facility Location: Applications and Theory","author":"Zvi Drezner","year":"2004","unstructured":"Drezner, Zvi, Hamacher, Horst W.: Facility Location: Applications and Theory. Springer, Berlin (2004)"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC \u201903: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 448\u2013455. ACM, New York, NY (2003)","DOI":"10.1145\/780542.780608"},{"key":"12_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Michael R Garey","year":"1979","unstructured":"Garey, Michael R., Johnson, David S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, NY (1979)"},{"key":"12_CR20","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: SODA \u201998: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 649\u2013657. Society for Industrial and Applied Mathematics, Philadelphia, PA (1998)"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC \u201902: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 731\u2013740. ACM, New York, NY (2002)","DOI":"10.1145\/509907.510012"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, pp. 2\u201313. IEEE Computer Society, Washington, DC (1999)","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: IEEE Symposium on Foundations of Computer Science, pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean kappa-median problem. In: Proceedings of the 7th Annual European Symposium on Algorithms, ESA \u201999, pp. 378\u2013389. Springer, London (1999)","DOI":"10.1007\/3-540-48481-7_33"},{"key":"12_CR25","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete algorithms, SODA \u201998, pp. 1\u201310. Society for Industrial and Applied Mathematics , Philadelphia, PA (1998)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Levi, R., Shmoys, D., Swamy, C.: LP-based Approximation Algorithms for Capacitated Facility Location. In: Bienstock, D., Nemhauser, G. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 3064, pp. 21\u201327. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-25960-2_16"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of the 38th International Conference on Automata, Languages and Programming, Vol. Part II, ICALP\u201911, pp. 77\u201388. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Lin, J.-H., Vitter, J.S.: e-approximations with minimum packing constraint violation (extended abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201992, pp. 771\u2013782. ACM, New York, NY (1992)","DOI":"10.1145\/129712.129787"},{"key":"12_CR29","volume-title":"Facilities Location: Models and Methods","author":"Robert F Love","year":"1988","unstructured":"Love, Robert F., Morris, James G., Wesolowsky, George O.: Facilities Location: Models and Methods. North-Holland, Amsterdam (1988)"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Di Battista, G., Zwick, U. (eds.) Algorithms\u2014ESA 2003. Lecture Notes in Computer Science, vol. 2832, pp. 409\u2013421. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: RANDOM-APPROX, pp. 129\u2013140 (2003)","DOI":"10.1007\/978-3-540-45198-3_12"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: APPROX, pp. 229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS \u201901, pp. 329\u2013338. IEEE Computer Society, Washington, DC (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"issue":"3","key":"12_CR34","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Progr. 62(3), 461\u2013474 (1993)","journal-title":"Math. Progr."},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"12_CR36","unstructured":"Verter, V.: Foundations of location analysis, chapter 2. International Series in Operations Research and Management Science. Springer, Berlin (2011)"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Zhang, J., Chen, B., Ye, Y.: A Multi-exchange local search algorithm for the capacitated facility location problem. In: Integer Programming and Combinatorial Optimization, pp. 1\u20134. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-25960-2_17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0012-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0012-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0012-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T00:57:33Z","timestamp":1566781053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0012-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,5]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["12"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0012-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,5]]}}}