School of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044, China

---

Abstract—In this paper, we present an approximation algorithm achieving approximation guarantee of 2 for the classical uncapacitated facility location problem. The distinguishing feature of our designed algorithm is the overall low running time of O(mlogm), where c f m=n ×n , c n and f n are the number of cities and facilities. Though the approximation factor is 1.61 in Ref.[1], whereas the running time is 3 O(n ) , where c f n=n+n . Compared with the approximation algorithm in Ref.[1], the advantage of our algorithm is it has more applications with lower running time.

Index Terms—Facility location problem, approximation algorithm, dual fitting, linear programming.

[PDF]

Cite: Wenhao Shu, "A Fast Algorithm for Facility Location Problem," Journal of Software vol. 8, no. 9, pp. 2360-2366, 2013.