Approximation algorithms for time-dependent orienteering

被引：56

作者：

Fomin, FV

Lingas, A

机构：

[1] Lund Univ, Dept Comp Sci, S-22100 Lund, Sweden

[2] Graduiertenkolleg PaSCo, Heinz Nixdorf Inst, D-33102 Paderborn, Germany

[3] Univ Gesamthsch Paderborn, D-33102 Paderborn, Germany

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 02期

关键词：

time-depending orienteering; traveling salesman; approximation algorithms; network design;

D O I：

10.1016/S0020-0190(01)00313-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For any epsilon > 0, we provide a (2 + epsilon)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：57 / 62

页数：6

共 16 条

[1] Arkin E. M., 1998, Proceedings of the Fourteenth Annual Symposium on Computational Geometry, P307, DOI 10.1145/276884.276919
[2] Awerbuch B., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P277, DOI 10.1145/225058.225139
[3] THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM
BALAS, E
[J]. NETWORKS, 1989, 19 (06) : 621 - 636
[4] Approximation algorithms for the TSP with sharpened triangle inequality
Böckenhauer, HJ
Hromkovic, J
Klasing, R
Seibert, S
Unger, W
[J]. INFORMATION PROCESSING LETTERS, 2000, 75 (03) : 133 - 138
[5] BRODEN B, 2000, THESIS LUND U SWEDEN
[6] CHERIYAN J, 1998, UNPUB APPROXIMATION
[7] Czumaj A, 1999, LECT NOTES COMPUT SC, V1663, P294
[8] Engebretsen L, 1999, LECT NOTES COMPUT SC, V1563, P373
[9] GOLDEN BG, 1991, NAVAL RES LOGIST, V34, P307
[10] Hammar M., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P392

← 1 2 →