Paths, Trees, and Minimum Latency Tours
- Kamalika Chaudhuri ,
- Brighten Godfrey ,
- Satish Rao ,
- Kunal Talwar
FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science |
Published by IEEE
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 ~O(n).
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.http://www.ieee.org/