Advanced

Approximation algorithms for time-dependent orienteering

Fomin, Fedor V. and Lingas, Andrzej LU (2002) In Information Processing Letters 83(2). p.57-62
Abstract
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 ε greater than or equal 0, we provide a (2+ ε)-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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Problem solving, Theorem proving, Optimization, Time-dependent orienteering, Algorithms, Polynomial approximation, Traveling salesman problem
in
Information Processing Letters
volume
83
issue
2
pages
57 - 62
publisher
Elsevier
external identifiers
  • wos:000175753800001
  • scopus:0037205795
ISSN
0020-0190
DOI
10.1016/S0020-0190(01)00313-1
language
English
LU publication?
yes
id
00066f8b-da59-455e-b95b-d0e05383fe46 (old id 113729)
date added to LUP
2007-07-23 13:58:37
date last changed
2017-10-29 04:23:57
@article{00066f8b-da59-455e-b95b-d0e05383fe46,
  abstract     = {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 ε greater than or equal 0, we provide a (2+ ε)-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.},
  author       = {Fomin, Fedor V. and Lingas, Andrzej},
  issn         = {0020-0190},
  keyword      = {Problem solving,Theorem proving,Optimization,Time-dependent orienteering,Algorithms,Polynomial approximation,Traveling salesman problem},
  language     = {eng},
  number       = {2},
  pages        = {57--62},
  publisher    = {Elsevier},
  series       = {Information Processing Letters},
  title        = {Approximation algorithms for time-dependent orienteering},
  url          = {http://dx.doi.org/10.1016/S0020-0190(01)00313-1},
  volume       = {83},
  year         = {2002},
}