Polynomial time approximation schemes for the traveling repairman and other minimum latency problems

René Sitters

We give a polynomial time, $(1+\epsilon )$-approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane and on weighted trees. This improves on the known quasi-…