Paths, trees, and minimum latency tours

被引：105

作者：

Chaudhuri, K ^{[1
]}

Godfrey, B ^{[1
]}

Rao, S ^{[1
]}

Talwar, K ^{[1
]}

机构：

[1] Univ Calif Berkeley, Berkeley, CA 94720 USA

来源：

44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2003年

关键词：

D O I：

10.1109/SFCS.2003.1238179

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give improved approximation algorithms for a variety of latency minimization problems. In particular we give a 3.59(1)-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of (O) over tilde (n).

引用

页码：36 / 45

页数：10

共 36 条

[1] THE COMPLEXITY OF THE TRAVELING REPAIRMAN PROBLEM [J].

AFRATI, F ;

COSMADAKIS, S ;

PAPADIMITRIOU, CH ;

PAPAGEORGIOU, G ;

PAPAKOSTANTINOU, N .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1986, 20 (01) :79-87

[2] A MEAN-VALUE ANALYSIS OF THE TRAVELING REPAIRMAN PROBLEM [J].

AGNIHOTHRI, SR .

IIE TRANSACTIONS, 1988, 20 (02) :223-229

[3]

ARCHER A, 2003, UNPUB FASTER APPROXI

[4]

Arora S., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P688, DOI 10.1145/301250.301432

[5]

Arora S, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P754

[6]

AUSIELLO G, 2000, LECT NOTES COMPUTER, V1767

[7] SALES-DELIVERY MAN PROBLEMS ON TREE-LIKE NETWORKS [J].

AVERBAKH, I ;

BERMAN, O .

NETWORKS, 1995, 25 (02) :45-58

[8]

BIANCO L, 1993, NETWORKS NETWORKS IN, V23

[9]

Blum A., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P163, DOI 10.1145/195058.195125

[10]

Blum A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P442, DOI 10.1145/237814.237992

← 1 2 3 4 →