Approximation algorithms for time-dependent orienteering
(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:
https://lup.lub.lu.se/record/113729
- author
- Fomin, Fedor V. and Lingas, Andrzej LU
- organization
- publishing date
- 2002
- 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
- 2016-04-01 17:00:18
- date last changed
- 2022-04-23 01:59:33
@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}}, keywords = {{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 = {{https://lup.lub.lu.se/search/files/4843884/623760.ps}}, doi = {{10.1016/S0020-0190(01)00313-1}}, volume = {{83}}, year = {{2002}}, }