Key points are not available for this paper at this time.
We are given a set of points p1;...;pn and a symmetric distance matrix (dij) givingthedistancebetweenpiandpj. Wewishtoconstruct atourthatminimizesPni=1`(i),where`(i)is thelatencyofpi,denedtobethedistance traveledbeforerstvisitingpi.Thisproblem isalsoknownintheliteratureasthedeliveryman problem orthetravelingrepairmanproblem. It arises in a number ofapplicationsincluding disk-head scheduling, and turnsouttobesurprisinglydierentfromthetravelingsalesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.
Blum et al. (Sat,) studied this question.