Approximation algorithms for time-dependent orienteering
Författare
Summary, in English
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.
Avdelning/ar
- Computer Science
Publiceringsår
2002
Språk
Engelska
Sidor
57-62
Publikation/Tidskrift/Serie
Information Processing Letters
Volym
83
Issue
2
Fulltext
- Available as AI - 178 kB
- Download statistics
Dokumenttyp
Artikel i tidskrift
Förlag
Elsevier
Ämne
- Computer Science
Nyckelord
- Problem solving
- Theorem proving
- Optimization
- Time-dependent orienteering
- Algorithms
- Polynomial approximation
- Traveling salesman problem
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 0020-0190