Paths, trees, and minimum latency tours
Kamalika Chaudhuri, Brighten Godfrey, Satish B. Rao, Kunal Talwar · 2004
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/sup /spl tilde//(n).