The minimum latency problem, also known as traveling repairman problem, is a variant of the TSP in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. We present a quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the nodes lie in Rd for some fixed d. The best polynomial time approximation algorithm due to Goemans and Kleinberg, computes a 3.59... approximation.
|Original language||English (US)|
|Number of pages||6|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1999|
|Event||Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA|
Duration: May 1 1999 → May 4 1999
All Science Journal Classification (ASJC) codes