A fast algorithm for facility location problem

被引：1

作者：

Shu, Wenhao ^{[1
]}

机构：

[1] School of Computer and Information Technology, Beijing Jiaotong University, Beijing

来源：

Journal of Software | 2013年 / 8卷 / 09期

关键词：

Approximation algorithm; Dual fitting; Facility location problem; Linear programming;

D O I：

10.4304/jsw.8.9.2360-2366

中图分类号：

学科分类号：

摘要：

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 m = nc × nf, nc and nf are the number of cities and facilities. Though the approximation factor is 1.61 in Ref.[1], whereas the running time is O(n3), where n=nc +nf. Compared with the approximation algorithm in Ref.[1], the advantage of our algorithm is it has more applications with lower running time. © 2013 ACADEMY PUBLISHER.

引用

页码：2360 / 2366

页数：6

共 29 条

[1]

Jain K., Mahdian M., Saberi A., A new greedy approach for facility location problems, Proceeding of the 30th Annual ACM symposium on Theory of Computing, pp. 731-740, (2002)

[2]

Guha S., Khuller S., Greedy strikes back: Improved facility location algorithms, Journal of Algorithms, 31, pp. 228-248, (1999)

[3]

Shmoys D.B., Tardos E., Aardal K., Approximation algorithms for facility location problems, Proceeding of the 29th ACM Symposium on Theory of Computing, pp. 265-274, (1997)

[4]

Chudak F., Shmoys D., Improved approximation algorithms for uncapacitated facility location, Integer Programming and Cominatorial Optimization, Springer LNCS, 1412, pp. 180-194, (1998)

[5]

Byrka J., Aardal K.I., An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM Journal on Computing, 39, 6, pp. 2212-2231, (2010)

[6]

Mahdian M., Ye Y., Zhang J., Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 2006, 36, 2, pp. 411-432, (2006)

[7]

Li S., A 1. 488 approximation algorithm for the uncapacitated facility location problem, Proceedings of ICALP, PART II, pp. 77-88, (2011)

[8]

Korupolu M.R., Plaxton C.G., Analysis of a Local Search Heuristic for Facility Location Problems, Journal of Algorithms, 37, 1, pp. 146-188, (2000)

[9]

Mahdian M., Markakis E., Saberi A., Vazirani V.V., A greedy facility location algorithm analyzed using dualfitting, Proceeding of 4th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 127-137, (2001)

[10]

Arya V., Garg N., Khandekar R., Munagala K., Pandit V., Local search heuristics for k-median and facility location problems, Proceedings of the 33th ACM Symposium on Theory of Computing, pp. 21-29, (2001)

← 1 2 3 →