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 条
  • [1] Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
    Gupta, Anupam
    Krishnaswamy, Ravishankar
    Nagarajan, Viswanath
    Ravi, R.
    MATHEMATICS OF OPERATIONS RESEARCH, 2015, 40 (01) : 56 - 79
  • [2] Evolutionary Algorithm for the Time-Dependent Orienteering Problem
    Ostrowski, Krzysztof
    COMPUTER INFORMATION SYSTEMS AND INDUSTRIAL MANAGEMENT (CISIM 2017), 2017, 10244 : 50 - 62
  • [3] Solving the stochastic time-dependent orienteering problem with time windows
    Verbeeck, C.
    Vansteenwegen, P.
    Aghezzaf, E. -H.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 255 (03) : 699 - 718
  • [4] Team orienteering problem with time windows and time-dependent scores
    Yu, Vincent F.
    Jewpanya, Parida
    Lin, Shih-Wei
    Redi, A. A. N. Perwira
    COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 127 : 213 - 224
  • [5] Model and Algorithm for Time-Dependent Team Orienteering Problem
    Li, Jin
    ADVANCED RESEARCH ON COMPUTER EDUCATION, SIMULATION AND MODELING, PT I, 2011, 175 : 1 - 7
  • [6] A fast solution method for the time-dependent orienteering problem
    Verbeeck, C.
    Soerensen, K.
    Aghezzaf, E. -H.
    Vansteenwegen, P.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 236 (02) : 419 - 432
  • [7] Approximation algorithms for the arc orienteering problem
    Gavalas, Damianos
    Konstantopoulos, Charalampos
    Mastakas, Konstantinos
    Pantziou, Grammati
    Vathis, Nikolaos
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 313 - 315
  • [8] Approximation Algorithms for the Team Orienteering Problem
    Xu, Wenzheng
    Xu, Zichuan
    Peng, Jian
    Liang, Weifa
    Liu, Tang
    Jia, Xiaohua
    Das, Sajal K.
    IEEE INFOCOM 2020 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, 2020, : 1389 - 1398
  • [9] TIME-DEPENDENT IMPULSE APPROXIMATION
    EPSTEIN, ST
    PHYSICAL REVIEW, 1960, 119 (01): : 458 - 460
  • [10] TIME-DEPENDENT ADIABATIC APPROXIMATION
    EPSTEIN, ST
    PHYSICAL REVIEW A, 1976, 14 (05): : 1929 - 1930
12345