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 条
  • [41] QUANTUM DYNAMICS IN A TIME-DEPENDENT VARIATIONAL APPROXIMATION
    COOPER, F
    PI, SY
    STANCIOFF, PN
    PHYSICAL REVIEW D, 1986, 34 (12): : 3831 - 3841
  • [42] POLYNOMIAL APPROXIMATION FOR TIME-DEPENDENT SLOWING DOWN
    KANG, S
    BECKER, M
    TRANSACTIONS OF THE AMERICAN NUCLEAR SOCIETY, 1974, 19 (OCT27): : 178 - 178
  • [43] Time-Dependent Performance Comparison of Evolutionary Algorithms
    Shilane, David
    Martikainen, Jarno
    Ovaska, Seppo J.
    ADAPTIVE AND NATURAL COMPUTING ALGORITHMS, 2009, 5495 : 223 - +
  • [44] Advances in Algorithms for Time-dependent Recommender Systems
    Kefalas, Pavlos
    Manolopoulos, Yannis
    2014 9TH INTERNATIONAL WORKSHOP ON SEMANTIC AND SOCIAL MEDIA ADAPTATION AND PERSONALIZATION (SMAP), 2014, : 38 - 43
  • [45] Time-Dependent Graphs: Definitions, Applications, and Algorithms
    Wang, Yishu
    Yuan, Ye
    Ma, Yuliang
    Wang, Guoren
    DATA SCIENCE AND ENGINEERING, 2019, 4 (04) : 352 - 366
  • [46] Time-Dependent Graphs: Definitions, Applications, and Algorithms
    Yishu Wang
    Ye Yuan
    Yuliang Ma
    Guoren Wang
    Data Science and Engineering, 2019, 4 : 352 - 366
  • [47] Time-dependent local-density approximation in real time
    Yabana, K
    Bertsch, GF
    PHYSICAL REVIEW B, 1996, 54 (07): : 4484 - 4487
  • [48] Efficient meta-heuristics for the Multi-Objective Time-Dependent Orienteering Problem
    Mei, Yi
    Salim, Flora D.
    Li, Xiaodong
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 254 (02) : 443 - 457
  • [49] Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications
    Xu, Wenzheng
    Liang, Weifa
    Xu, Zichuan
    Peng, Jian
    Peng, Dezhong
    Liu, Tang
    Jia, Xiaohua
    Das, Sajal K.
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2021, 29 (01) : 176 - 189
  • [50] Optimal routing policy problems in stochastic time-dependent networks part II: Exact and approximation algorithms
    Gao, S
    Chabini, I
    IEEE 5TH INTERNATIONAL CONFERENCE ON INTELLIGENT TRANSPORTATION SYSTEMS, PROCEEDINGS, 2002, : 555 - 559
12345