The minimum latency problem
Avrim L. Blum, Prasad Chalasani, Don Coppersmith et al. · ACM Symposium on Theory of Computing (STOC) · 1994
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.
Cited by 319 works. doi:10.1145/195058.195125
Authors
References
- A General Approximation Technique for Constrained Forest Problems
- The Traveling Salesman Problem with Distances One and Two
- Shortest paths without a map
- A note on the prize collecting traveling salesman problem
- The complexity of the travelling repairman problem
- Searching with uncertainty
- An O (log k ) approximation algorithm for the k minimum spanning tree problem in the plane
- Time‐dependent traveling salesman problem–the deliveryman case
- The delivery man problem on a tree network
- The traveling salesman problem with cumulative costs