{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:34:34Z","timestamp":1792071274974,"version":"4.4.0"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is $1.463\\dots$. An algorithm is a ($\\lambda_f$,$\\lambda_c$)-approximation algorithm if the solution it produces has total cost at most $\\lambda_f\\cdot F^*+\\lambda_c\\cdot C^*$, where $F^*$ and $C^*$ are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the $(1+2\/e)$-approximation algorithm of Chudak and Shmoys, is a $(1.6774,1.3738)$-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve $(\\gamma_f,1+2e^{-\\gamma_f})$ established by Jain, Mahdian, and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a $(1.11,1.7764)$-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL.<\/jats:p>","DOI":"10.1137\/070708901","type":"journal-article","created":{"date-parts":[[2010,3,17]],"date-time":"2010-03-17T18:06:09Z","timestamp":1268849169000},"page":"2212-2231","source":"Crossref","is-referenced-by-count":111,"title":["An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem"],"prefix":"10.1137","volume":"39","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karen","family":"Aardal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,3,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00144-1"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Ageev, Y. Ye, and J. Zhang,\n                      \n                        Improved combinatorial approximation algorithms for the\n                        k\n                        -level facility location problem\n                      \n                      , in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci. 2719, Springer, Berlin, 2003, pp. 145\u2013156.","DOI":"10.1007\/3-540-45061-0_13"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Arora, P. Raghavan, and S. Rao,\n                      \n                        Approximation schemes for Euclidean\n                        k\n                        -medians and related problems\n                      \n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1998, pp. 106\u2013113.","DOI":"10.1145\/276698.276718"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. Byrka,\n                      An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem\n                      , in Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Note in Comput. Sci. 4627, Springer, Berlin, 2007, pp. 29\u201343.","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.03.017"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha,\n                      \n                        Improved combinatorial algorithms for facility location and\n                        k\n                        -median problems\n                      \n                      , in Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 378\u2013388.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"F. A. Chudak,\n                      Improved approximation algorithms for uncapacitated facility location\n                      , in Proceedings of the 6th Integer Programing and Combinatorial Optimization (IPCO), Lecture Note in Comput. Sci. 1412, Springer, Berlin, 1998, pp. 180\u2013194.","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.1287\/mnsc.23.8.789"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"R14","unstructured":"S. Guha and S. Khuller,\n                      Greedy strikes back: Improved facility location algorithms\n                      , in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 1998, pp. 649\u2013657."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"R16","unstructured":"M. Hazewinkel, ed.\n                      Encyclopedia of Mathematics\n                      , Springer, Berlin, 2002, http:\/\/eom.springer.de\/default.htm."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581035"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"K. Jain, M. Mahdian, and A. Saberi,\n                      A new greedy approach for facility location problems\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2002, pp. 731\u2013740.","DOI":"10.1145\/509907.510012"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J.H. Lin and J. S. Vitter,\n                      $\\epsilon$-approximations with minimum packing constraint violation\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. Mahdian, Y. Ye, and J. Zhang,\n                      Improved approximation algorithms for metric facility location problems\n                      , in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Note in Comput. Sci. 2462, Springer, Berlin, 2002, pp. 229\u2013242.","DOI":"10.1007\/3-540-45753-4_20"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys,\n                      Approximation algorithms for facility location problems\n                      , in Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Comput. Sci. 1913, Springer, Berlin, 2000, pp. 265\u2013274.","DOI":"10.1007\/3-540-44436-X_4"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. Aardal,\n                      Approximation algorithms for facility location problems (extended abstract)\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Sviridenko,\n                      An improved approximation algorithm for the metric uncapacitated facility location problem\n                      , in Proceedings of the 9th Integer Programming and Combinatorial Optimization (IPCO), Lecture Note in Comput. Sci. 2337, Springer, Berlin, 2002, pp. 240\u2013257.","DOI":"10.1007\/3-540-47867-1_18"},{"key":"R25","unstructured":"J. Vygen,\n                      Approximation Algorithms for Facility Location Problems (Lecture Notes)\n                      , Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, 2005; available online from http:\/\/www.or.uni-bonn.de\/$\\!_{^{\\sim}}\\!$vygen\/fl.pdf."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0704-x"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070708901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:32Z","timestamp":1787337392000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070708901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070708901"],"URL":"https:\/\/doi.org\/10.1137\/070708901","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}