Faster approximation algorithms for the minimum latency problem
Aaron F. Archer, David P. Williamson · 2003
In this paper, we give a 9.28-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-MST problem which is called as a black box. Their algorithm can achieve a performance guarantee of 10.77 while making O(n PCST calls (via a k-MST algorithm of Garg), or a performance guarantee of 7.18+ # while using n O(1/#) PCST calls (via a k-MST algorithm of Arora and Karakostas). In order to match our approximation ratio (i.e. setting # = 2.10), the latter version requires n) PCST calls, so our running time bound is faster by a factor of #(n log n). Since PCST can be implemented to run in O(n ) time, the overall running time of our algorithm is O(n log n).