The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximation algorithms for time-dependent orienteering

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

57-62

Publication/Series

Information Processing Letters

Volume

83

Issue

2

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • Problem solving
  • Theorem proving
  • Optimization
  • Time-dependent orienteering
  • Algorithms
  • Polynomial approximation
  • Traveling salesman problem

Status

Published

ISBN/ISSN/Other

  • ISSN: 0020-0190