Paths, trees, and minimum latency tours

Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar

Research output: Contribution to journalConference articlepeer-review


We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.591-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of Õ(n).

Original languageEnglish (US)
Pages (from-to)36-45
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2003
Externally publishedYes
EventProceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States
Duration: Oct 11 2003Oct 14 2003

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Paths, trees, and minimum latency tours'. Together they form a unique fingerprint.

Cite this