Computer Science – Data Structures and Algorithms
Scientific paper
2007-03-02
Computer Science
Data Structures and Algorithms
A journal version
Scientific paper
We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location problem (UFL), 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. An algorithm is a {\em ($\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.
Aardal Karen
Byrka Jaroslaw
No associations
LandOfFree
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-284500