PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
The problem is more commonly known as the “Traveling Repairman Problem” (TRP) or the “Minimum Latency Problem”. It is, of course, NP-hard. The best approximation algorithm finds a solution in polynomial time that is guaranteed to have the average waiting time no more than 3.59 times the optimal 1. The heart of the algorithm lies in approximating the minimum cost of a rooted k-trees which are minimum cost trees containing a given node and any k-1 other nodes.
At first, the problem might seem very similar to the more popular Traveling Salesman Path Problem (TSPP) where the goal is to visit all locations as fast as possible without the requirement that we must end where we started. However, there are simple instances where the optimum TSPP solutions looks quite different than the optimum TRP problem. Consider the following graph which is viewed as points on the real line. We start at location 0 and each location 0 < i < n is at point (-2)^i. The optimum TSP solution visits all nodes < 0 then all nodes > 0 (or vice-versa depending on whether n is odd or even) whereas the optimum TRP solution zig-zags back and forth across 0.
- K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar, “Paths, trees, and minimum latency tours”, in Proceedings of Foundations of Computer Science, pp 36-45, 2003.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.