Paths, Trees, and Minimum Latency Tours

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).

Authors

• Kamalika Chaudhuri
• Philip Brighten Godfrey
• Satish Rao
• Kunal Talwar

Keywords

• Delay
• Approximation algorithms
• Computer science
• Cost function
• Minimization methods
• Space exploration
• Tree graphs
• Educational institutions
• Equations
• Minimum Latency
• Rest Of The Paper
• Related Problems
• Estimation Algorithm
• Minimization Problem
• Previous Algorithms
• Roots Of Equation
• Interpolation
• Lower Bound
• Growth Phase
• Running Time
• Linear Programming
• Shortest Path
• Feasible Solution
• Problem Of Finding
• Algorithm For Problem
• Version Of Problem
• Good Clustering
• Tree Pruning
• General Metrics
• Dual Solution
• Primal-dual Algorithm
• Real Tree
• Polylogarithmic
• Linear Programming Relaxation
• Set Cover Problem