The A Priori Traveling Repairman Problem

Martijn van Ee*, R.A. Sitters

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP.

Original languageEnglish
Pages (from-to)2818–2833
Number of pages16
JournalAlgorithmica
Volume80
Issue number10
Early online date28 Jul 2017
DOIs
Publication statusPublished - Oct 2018

Funding

The authors are supported by the NWO Grant 612.001.215.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek612.001.215

    Keywords

    • A priori optimization
    • Approximation algorithms
    • Traveling repairman problem

    Fingerprint

    Dive into the research topics of 'The A Priori Traveling Repairman Problem'. Together they form a unique fingerprint.

    Cite this