Given a tour visiting n points in a metric space, the latency of one of these points p is the distance traveled in the tour before reaching p. The minimum latency problem (MLP) asks for a tour passing through n given points for which the total latency of the n points is minimum; in effect, we are seeking the tour with minimum average ‘arrival time’. This problem has been studied in the operations research literature, where it has also been termed the ‘delivery-man problem’ and the ‘traveling repairman problem’. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally.
