Faster approximation algorithms for the minimum latency problem

Abstract

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(n2 log n) PCST calls (via a k-MST algorithm of Garg), or a performance guarantee of 7.18 + ε while using nO(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 O(n5 log2n) PCST calls, so our running time bound is faster by a factor of θ(n4 log n). Since PCST can be implemented to run in O(n2) time, the overall running time of our algorithm is O(n3 log n). The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. Thus we are able to take advantage of some situations in which the PCST subroutine delivers a k-MST with an improved performance guarantee.