{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T18:52:21Z","timestamp":1787597541569,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of $2.414+\\epsilon$ in $\\tilde{O}(n^2\/\\epsilon)$ time. This also yields a bicriteria approximation tradeoff of $(1+\\gamma,1+2\/\\gamma)$ for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of $1.853$ in $\\tilde{O}(n^3)$ time. This is very close to the approximation guarantee of the best known algorithm which is linear programming (LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving $1.728$. We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this.<\/jats:p>","DOI":"10.1137\/s0097539701398594","type":"journal-article","created":{"date-parts":[[2005,5,18]],"date-time":"2005-05-18T21:00:21Z","timestamp":1116450021000},"page":"803-824","source":"Crossref","is-referenced-by-count":118,"title":["Improved Combinatorial Algorithms for Facility Location Problems"],"prefix":"10.1137","volume":"34","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Prabhakar Raghavan, Satish Rao, Approximation schemes for Euclidean k\u2010medians and related problems, ACM, New York, 1999, 106\u2013113MR1731569","DOI":"10.1145\/276698.276718"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1047"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Yair Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 184\u2013193MR1450616","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k\u2010median, ACM, New York, 1999, 114\u2013123MR1731567","DOI":"10.1145\/276698.276719"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Moses Charikar, Sudipto Guha, Improved combinatorial algorithms for the facility location and k\u2010median problems, IEEE Computer Soc., Los Alamitos, CA, 1999, 378\u2013388MR1917576","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Fabi\u00e1n Chudak, Improved approximation algorithms for uncapacitated facility location, Lecture Notes in Comput. Sci., Vol. 1412, Springer, Berlin, 1998, 180\u20131942000j:90017","DOI":"10.1007\/3-540-69346-7_14"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Fabi\u00e1n Chudak, David Williamson, Improved approximation algorithms for capacitated facility location problems, Lecture Notes in Comput. Sci., Vol. 1610, Springer, Berlin, 1999, 99\u20131132000i:90026","DOI":"10.1007\/3-540-48777-8_8"},{"key":"R13","unstructured":"G\u00e9rard Cornu\u00e9jols, George Nemhauser, Laurence Wolsey, The uncapacitated facility location problem, Wiley\u2010Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1990, 119\u2013171MR1066259"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90002-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Piotr Indyk, Sublinear time algorithms for metric space problems, ACM, New York, 1999, 428\u2013432MR1798064","DOI":"10.1145\/301250.301366"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Kamal Jain, Mohammad Mahdian, Amin Saberi, A new greedy approach for facility location problems, ACM, New York, 2002, 731\u2013740MR2121521","DOI":"10.1145\/509907.510012"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329776"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1100"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.643"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90208-D"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J.\u2010H. Lin and J. S. Vitter,\n                      \u03b5\u2010approximations with minimum packing constraint violation\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay Vazirani, A greedy facility location algorithm analyzed using dual fitting, Lecture Notes in Comput. Sci., Vol. 2129, Springer, Berlin, 2001, 127\u20131372003d:90049","DOI":"10.1007\/3-540-44666-4_16"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Mohammad Mahdian, Yinyu Ye, Jiawei Zhang, Improved approximation algorithms for metric facility location problems, Lecture Notes in Comput. Sci., Vol. 2462, Springer, Berlin, 2002, 229\u2013242MR2091829","DOI":"10.1007\/3-540-45753-4_20"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0930"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"R31","unstructured":"D. B. Shmoys,\n                      personal communication\n                      , 1999."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. I. Aardal,\n                      Approximation algorithms for facility location problems\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"R34","unstructured":"M. Sviridenko,\n                      personal communication\n                      , 1998."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(96)00021-1"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup, Quick k\u2010median, k\u2010center, and facility location for sparse graphs, Lecture Notes in Comput. Sci., Vol. 2076, Springer, Berlin, 2001, 249\u2013260MR2065867","DOI":"10.1007\/3-540-48224-5_21"},{"key":"R37","unstructured":"S. de Vries, M. Posner, and R. Vohra,\n                      The K\u2010Median Problem on a Tree\n                      , working paper, Ohio State University, Columbus, OH, 1998."},{"key":"R38","unstructured":"J. Ward, R. T. Wong, P. Lemke, and A. Oudjit,\n                      Properties of the Tree K\u2010Median Linear Programming Relaxation\n                      , Research report CC\u2010878\u201029, Institute for Interdisciplinary Engineering Studies, Purdue University, West Lafayette, IN, 1987."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539701398594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:12Z","timestamp":1787336172000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539701398594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539701398594"],"URL":"https:\/\/doi.org\/10.1137\/s0097539701398594","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}