Approximation schemes for minimum latency problems

被引：28

作者：

Arora, S ^{[1
]}

Karakostas, G

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

[2] McMaster Univ, Dept Comp & Software, Hamilton, ON L8S 4K1, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2003年 / 32卷 / 05期

关键词：

minimum latency tour; traveling repairman; search ratio; randomized search ratio; vehicle routing; quasi-polynomial approximation schemes; approximation algorithms;

D O I：

10.1137/S0097539701399654

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The minimum latency problem, also known as the traveling repairman problem, is a variant of the traveling salesman problem in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. We present a quasi-polynomial time approximation scheme (QPTAS) for this problem when the instance is a weightedtree, when the nodes lie in R-d for some fixed d, and for planar graphs. We also present a polynomial time constant factor approximation algorithm for the general metric case. The currently best polynomial time approximation algorithm for general metrics, due to Goemans and Kleinberg, computes a 3.59-approximation.

引用

页码：1317 / 1337

页数：21

共 20 条

[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] ON SPARSE SPANNERS OF WEIGHTED GRAPHS [J].

ALTHOFER, I ;

DAS, G ;

DOBKIN, D ;

JOSEPH, D ;

SOARES, J .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (01) :81-100

[3]

Archer A, 2003, SIAM PROC S, P88

[4]

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

[5] Proof verification and the hardness of approximation problems [J].

Arora, S ;

Lund, C ;

Motwani, R ;

Sudan, M ;

Szegedy, M .

JOURNAL OF THE ACM, 1998, 45 (03) :501-555

[6] Polynomial time approximation schemes for euclidean TSP and other geometric problems [J].

Arora, S .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :2-11

[7]

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

[8]

ARORA S, 1998, J ACM, V45, P1

[9]

Arora Sanjeev, 1998, P 9 ANN ACM SIAM S D, P33

[10] THE TRAVELING SALESMAN PROBLEM WITH CUMULATIVE COSTS [J].

BIANCO, L ;

MINGOZZI, A ;

RICCIARDELLI, S .

NETWORKS, 1993, 23 (02) :81-91

← 1 2 →