Paths, trees, and minimum latency tours

K. Chaudhuri, B. Godfrey, S. Rao, K. Talwar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.59-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)
Title of host publicationProceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
PublisherIEEE Computer Society
Pages36-45
Number of pages10
ISBN (Electronic)0769520405
DOIs
StatePublished - 2003
Externally publishedYes
Event44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States
Duration: Oct 11 2003Oct 14 2003

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2003-January
ISSN (Print)0272-5428

Other

Other44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
CountryUnited States
CityCambridge
Period10/11/0310/14/03

Keywords

  • Approximation algorithms
  • Computer science
  • Cost function
  • Delay
  • Educational institutions
  • Equations
  • Minimization methods
  • Space exploration
  • Tree graphs

ASJC Scopus subject areas

  • Computer Science(all)

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

Cite this