@inproceedings{9a4ecb8fd5ec49318df61c7f2a7ca893,
title = "Paths, trees, and minimum latency tours",
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 {\~O}(n).",
keywords = "Approximation algorithms, Computer science, Cost function, Delay, Educational institutions, Equations, Minimization methods, Space exploration, Tree graphs",
author = "K. Chaudhuri and B. Godfrey and S. Rao and K. Talwar",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",
year = "2003",
doi = "10.1109/SFCS.2003.1238179",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "36--45",
booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",
}