TY - GEN

T1 - An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

AU - Byrka, J.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-74207

DO - 10.1007/978-3-540-74207

M3 - Conference contribution

SN - 978-3-540-74207-4

T3 - Lecture Notes in Computer Science

SP - 29

EP - 43

BT - 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

A2 - Charikar, M.

A2 - Jansen, K.

A2 - Reingold, O.

A2 - Rolim, J.D.P.

PB - Springer

CY - Berlin

T2 - conference; APPROX 2007 and RANDOM 2007, Princeton, New Jersey, USA; 2007-08-20; 2007-08-22

Y2 - 20 August 2007 through 22 August 2007

ER -