Approximation algorithms for time-dependent orienteering

Fedor V. Fomin, Andrzej Lingas

    Research output: Contribution to journalArticlepeer-review

    57 Citations (SciVal)
    51 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)57-62
    JournalInformation Processing Letters
    Volume83
    Issue number2
    DOIs
    Publication statusPublished - 2002

    Subject classification (UKÄ)

    • Computer Science

    Keywords

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

    Fingerprint

    Dive into the research topics of 'Approximation algorithms for time-dependent orienteering'. Together they form a unique fingerprint.

    Cite this