An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing rounding algorithm is the first one that touches the approximability limit curve $(\gamma_f, 1+2e^{-\gamma_f})$ established by Jain et al. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. Our new algorithm - when combined with a (1.11,1.7764)-approxima- tion algorithm proposed by Jain, Mahdian and Saberi, and later analyzed by Mahdian, Ye and Zhang - gives a 1.5-approximation algorithm for the metric UFL problem. This algorithm improves over the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang, and it cuts the gap with the approximability lower bound by 1/3. The algorithm is also used to improve the approximation ratio for the 3-level version of the problem.

Published in:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007., 29-43
Presented at:
10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Princeton, NJ, USA, August 20-22, 2007

 Record created 2009-06-12, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)