Approximation algorithms for time-dependent orienteering

Research output: Contribution to journalArticle

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.

Details

Authors
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • Problem solving, Theorem proving, Optimization, Time-dependent orienteering, Algorithms, Polynomial approximation, Traveling salesman problem
Original languageEnglish
Pages (from-to)57-62
JournalInformation Processing Letters
Volume83
Issue number2
StatePublished - 2002
Publication categoryResearch
Peer-reviewedYes

Total downloads

No data available