Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 36-45 |
| Number of pages | 10 |
| Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
| State | Published - 2003 |
| Externally published | Yes |
| Event | Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States Duration: Oct 11 2003 → Oct 14 2003 |
ASJC Scopus subject areas
- Hardware and Architecture