Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

We give a polynomial time approximation scheme for the weighted traveling repairman problem (TRP) in the Euclidean plane, on trees, and on planar graphs. This improves upon the quasi-polynomial time approximation schemes for the unweighted TRP in the Euclidean plane and trees and on the 3.59-approximation for planar graphs. The algorithms are based on a new decomposition technique that reduces the approximation of weighted TRP to instances for which we may restrict ourselves to solutions that are the concatenation of only a constant number of traveling salesman problem paths. A similar reduction applies to many other problems with an average completion time objective. To illustrate the strength of this approach, we apply the same technique to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, $1|prec|\sum w_{j}C_{j}$, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem.