Journal article
Approximation algorithms for the a priori traveling repairman
We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem. Given a metric (V,d) with a root r∈V, the traveling repairman problem (TRP) involves finding a tour originating from r that minimizes the sum of arrival-times at all vertices.
In its a priori version, we are also given independent probabilities of each vertex being active. We want to find a master tour τ originating from r and visiting all vertices. The objective is to minimize the expected sum of arrival-times at all active vertices, when τ is shortcut over the inactive vertices.
We obtain the first constant-factor approximation algorithm for a priori TRP under independent non-uniform probabilities. Our result provides a general reduction from non-uniform to uniform probabilities, and uses (in black-box manner) an existing approximation algorithm for a priori TRP under uniform probabilities.
Language: | English |
---|---|
Year: | 2020 |
Pages: | 599-606 |
ISSN: | 18727468 and 01676377 |
Types: | Journal article |
DOI: | 10.1016/j.orl.2020.07.009 |
ORCIDs: | 0000-0002-9514-5581 and Gørtz, Inge Li |