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
相关论文
共 50 条
  • [31] Time-Dependent Gutzwiller Approximation: Theory and Applications
    Noatschk, K.
    Martens, C.
    Seibold, G.
    JOURNAL OF SUPERCONDUCTIVITY AND NOVEL MAGNETISM, 2020, 33 (08) : 2389 - 2393
  • [32] Time-Dependent Gutzwiller Approximation: Theory and Applications
    K. Noatschk
    C. Martens
    G. Seibold
    Journal of Superconductivity and Novel Magnetism, 2020, 33 : 2389 - 2393
  • [33] Improved Approximation for Time-Dependent Shortest Paths
    Omran, Masoud
    Sack, Joerg-Ruediger
    COMPUTING AND COMBINATORICS, COCOON 2014, 2014, 8591 : 453 - 464
  • [34] The time-dependent Born-Oppenheimer approximation
    Panati, Gianluca
    Spohn, Herbert
    Teufel, Stefan
    ESAIM-MATHEMATICAL MODELLING AND NUMERICAL ANALYSIS-MODELISATION MATHEMATIQUE ET ANALYSE NUMERIQUE, 2007, 41 (02): : 297 - 314
  • [35] ACCURACY OF THE SEMICLASSICAL APPROXIMATION FOR THE TIME-DEPENDENT PROPAGATOR
    SCHULMAN, LS
    JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1994, 27 (05): : 1703 - 1721
  • [36] A NUMERICAL SOLUTION OF TIME-DEPENDENT DPL APPROXIMATION
    KNICKLE, HN
    DAITCH, PB
    TRANSACTIONS OF THE AMERICAN NUCLEAR SOCIETY, 1969, 12 (01): : 155 - &
  • [37] Time-Dependent Gutzwiller Approximation: Interplay with Phonons
    Seibold, G.
    Buenemann, J.
    Lorenzana, J.
    JOURNAL OF SUPERCONDUCTIVITY AND NOVEL MAGNETISM, 2014, 27 (04) : 929 - 931
  • [38] Instability in the first approximation for time-dependent linearizations
    Leonov, GA
    PMM JOURNAL OF APPLIED MATHEMATICS AND MECHANICS, 2002, 66 (02): : 323 - 325
  • [39] AN ADIABATIC APPROXIMATION FOR TIME-DEPENDENT CONSTANTS OF THE MOTION
    WULFMAN, CE
    LEVINE, RD
    CHEMICAL PHYSICS LETTERS, 1981, 84 (01) : 13 - 16
  • [40] TIME-DEPENDENT TRANSPORT PROCESSES IN ADIABATIC APPROXIMATION
    FALL, SM
    PHYSICS LETTERS A, 1974, A 49 (04) : 297 - 298
12345