Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP

被引：296

作者：

Jain, K ^{[1
]}

Mahdian, M

Markakis, E

Saberi, A

Vazirani, VV

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

[2] MIT, Comp Sci Lab, Cambridge, MA 02139 USA

[3] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA

来源：

JOURNAL OF THE ACM | 2003年 / 50卷 / 06期

关键词：

approximation algorithms; dual-fitting method; facility location problem; primal-dual method;

D O I：

10.1145/950620.950621

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n(3)), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

引用

页码：795 / 824

页数：30

共 44 条

[1]

ANDREWS M, 1998, P 39 ANN IEEE S FDN

[2]

[Anonymous], 1999, 40 ANN S FDN COMP SC

[3]

ARYA V, 2001, P 33 ACM S THEOR COM

[4]

Balinski M, 1966, P IBM SCI COMP S COM, P225

[5]

BEASLEY JE, 2002, OPERATIONS RES LIB

[6]

CAMERON C, 2002, P ACM SIGMETRICS JUN, P152

[7]

Charikar M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P1, DOI 10.1145/301250.301257

[8]

CHARIKAR M, 2001, 12 ANN ACM SIAM S DI

[9]

Chudak FA, 1998, LECT NOTES COMPUT SC, V1412, P180

[10]

CHUDAK FA, 1998, UNPUB IMPROVED APPRO

← 1 2 3 4 5 →