Quick and good facility location

被引：0

作者：

Thorup, M ^{[1
]}

机构：

[1] AT&T Labs Res, Florham Pk, NJ 07932 USA

来源：

PROCEEDINGS OF THE FOURTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2003年

关键词：

efficient approximation algorithms; shortest paths; facility location;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider the facility location problem with shortest path distances in a weighted graph. W.h.p., we get an approximation factor of 1.62 in (O) over tilde (n + m) time with n and m the number of nodes and edges. Also, as a kind of warm-up, for a metric with a constant-times distance oracle, we get the factor 1.62 deterministically in O(n(2) log n) time. Our results build on a recent facility location algorithm of Jain, Mahdian, and Saberi (STOC'02) achieving an approximation factor of 1.61 in O(n(3)) time.

引用

页码：178 / 185

页数：8

共 18 条

[1] [Anonymous], P 20 ANN JOINT C IEE
[2] Carey M., 1979, COMPUTER INTRACTABIL
[3] Size-estimation framework with applications to transitive closure and reachability
Cohen, E
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 55 (03) : 441 - 453
[4] Cole R, 2001, SIAM PROC S, P17
[5] Cormen T. H., 1990, INTRO ALGORITHMS
[6] Clustering data streams
Guha, S
Mishra, N
Motwani, R
O'Callaghan, L
[J]. 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 359 - 366
[7] Greedy strikes back: Improved facility location algorithms
Guha, S
Khuller, S
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01): : 228 - 248
[8] Indyk P., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P428, DOI 10.1145/301250.301366
[9] A HEURISTIC PROGRAM FOR LOCATING WAREHOUSES
KUEHN, AA
HAMBURGER, MJ
[J]. MANAGEMENT SCIENCE, 1963, 9 (04) : 643 - 665
[10] Mahdian M, 2001, LECT NOTES COMPUT SC, V2129, P127

← 1 2 →