A new approximation algorithm for the k-facility location problem

AbstractThe k-facility location problem is a common generalization of the facility location and the k-median problems. For the metric uncapacitated k-facility location problem, we propose a polynomial-time 2+3+ϵ-approximation algorithm using the local search approach, which significantly improves the previously known approximation ratio 4, given by Jain et al. using the greedy method [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM 50 (2003) 795–824]