2014
Polynomial time approximation schemes for the traveling repairman and other minimum latency problems
Publication
Publication
Presented at the
SIAM Conference on Discrete Mathematics, Portland, Oregon, USA
We give a polynomial time, (1 + ∊)approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane, on weighted planar graphs, and on weighted trees. This improves on the known quasipolynomial time approximation schemes for these problems. The algorithm is based on a simple technique that reduces the TRP to what we call the segmented TSP. Here, we are given numbers l1, …, lK and n1, …, nK and we need to find a path that visits at least nh points within path distance lh from the starting point for all h ∊ {1, …, K}. A solution is αapproximate if at least nh points are visited within distance αlh. It is shown that any algorithm that is αapproximate for every constant K in some metric space, gives an α(1 + ∊)approximation for the TRP in the same metric space. Subsequently, approximation schemes are given for this segmented TSP problem in different metric spaces. The segmented TSP with only one segment (K = 1) is equivalent to the kTSP for which a (2 + ∊)approximation is known for a general metric space. Hence, this approach through the segmented TSP gives new impulse for improving on the 3.59approximation for TRP in a general metric space. A similar reduction applies to many other minimum latency problems. To illustrate the strength of this approach we apply it to the wellstudied scheduling problem of minimizing total weighted completion time under precedence constraints, 1precΣ wjCj, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2approximation for this problem. Both approximation schemes apply as well if release dates are added to the problem.
Additional Metadata  

SIAM  
C. Chekuri  
SIAM Conference on Discrete Mathematics  
Organisation  Networks and Optimization 
Sitters, R.A. (2014). Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. In C Chekuri (Ed.), . SIAM.
