๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximation algorithms for time-dependent orienteering

โœ Scribed by Fedor V. Fomin; Andrzej Lingas

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
73 KB
Volume
83
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 any ฮต > 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.

๐Ÿ“œ SIMILAR VOLUMES

Polynomial time approximation algorithms
Polynomial time approximation algorithms for machine scheduling: ten open problems
โœ Petra Schuurman; Gerhard J. Woeginger ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Springer US ๐ŸŒ English โš– 91 KB ๐Ÿ‘ 2 views

We discuss what we consider to be the 10 most vexing open questions in the area of polynomial time approximation algorithms for NP-hard deterministic machine scheduling problems. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature. Copy