Approximation schemes for minimum latency problems

Sanjeev Arora, George Karakostas

Research output: Contribution to journalConference articlepeer-review

35 Scopus citations


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 languageEnglish (US)
Pages (from-to)688-693
Number of pages6
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Approximation schemes for minimum latency problems'. Together they form a unique fingerprint.

Cite this