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 language | English |
---|---|
Pages (from-to) | 2818–2833 |
Number of pages | 16 |
Journal | Algorithmica |
Volume | 80 |
Issue number | 10 |
Early online date | 28 Jul 2017 |
DOIs | |
Publication status | Published - Oct 2018 |
Funding
The authors are supported by the NWO Grant 612.001.215.
Funders | Funder number |
---|---|
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 612.001.215 |
Keywords
- A priori optimization
- Approximation algorithms
- Traveling repairman problem