An improved approximation ratio for the minimum latency problem
Michel X. Goemans, Jon M. Kleinberg · 1996
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 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 minimum latency problem was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem, it is not easy to give any constant-factor approximation algorithm for the minimum latency problem. Recently, Blum, Chalasani, Coppersmith, Pulleyblank, Raghavan, and Sudan gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we present an algorithm which improves this ratio to 21:55. The dev...