TY - GEN
T1 - A 1.488 approximation algorithm for the uncapacitated facility location problem
AU - Li, Shi
PY - 2011
Y1 - 2011
N2 - We present a 1.488 approximation algorithm for the metric uncapacitated facility location (UFL) problem. Previously the best algorithm was due to Byrka [1]. By linearly combining two algorithms A1(γf) for γf ≈ 1.6774 and the (1.11,1.78)-approximation algorithm A2 proposed by Jain, Mahdian and Saberi [8], Byrka gave a 1.5 approximation algorithm for the UFL problem. We show that if γf is randomly selected from some distribution, the approximation ratio can be improved to 1.488. Our algorithm cuts the gap with the 1.463 approximability lower bound by almost 1/3.
AB - We present a 1.488 approximation algorithm for the metric uncapacitated facility location (UFL) problem. Previously the best algorithm was due to Byrka [1]. By linearly combining two algorithms A1(γf) for γf ≈ 1.6774 and the (1.11,1.78)-approximation algorithm A2 proposed by Jain, Mahdian and Saberi [8], Byrka gave a 1.5 approximation algorithm for the UFL problem. We show that if γf is randomly selected from some distribution, the approximation ratio can be improved to 1.488. Our algorithm cuts the gap with the 1.463 approximability lower bound by almost 1/3.
KW - Approximation
KW - Facility Location Problem
KW - Theory
UR - https://www.scopus.com/pages/publications/79960012691
U2 - 10.1007/978-3-642-22012-8_5
DO - 10.1007/978-3-642-22012-8_5
M3 - Conference contribution
SN - 9783642220111
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 77
EP - 88
BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011
Y2 - 4 July 2011 through 8 July 2011
ER -