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 -