2010
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
Publication
Publication
SIAM Journal on Computing , Volume 39 - Issue 6 p. 2212- 2231
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.
Additional Metadata | |
---|---|
, , | |
SIAM | |
SIAM Journal on Computing | |
Algorithmic Optimization Discretization | |
Organisation | Networks and Optimization |
Byrka, J., & Aardal, K. (2010). An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. SIAM Journal on Computing, 39(6), 2212–2231. |