Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.