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 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.
|Title of host publication||Proceedings of the 10th International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX 2007) and of the 11th International Workshop (RANDOM 2007) 20-22 August 2007, Princeton, New Jersey, USA|
|Editors||M. Charikar, K. Jansen, O. Reingold, J.D.P. Rolim|
|Place of Publication||Berlin|
|Publication status||Published - 2007|
|Event||conference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22 - |
Duration: 20 Aug 2007 → 22 Aug 2007
|Name||Lecture Notes in Computer Science|
|Conference||conference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22|
|Period||20/08/07 → 22/08/07|
|Other||APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA|