A Faster, Better Approximation Algorithm for the Minimum Latency Problem

We give a 7.18-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. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the $k$-minimum spanning tree ($k$-MST) problem which is called as a black box for each value of $k$. Their algorithm can achieve an approximation factor of 10.77 while making $O(n (n+\log C) \log n)$ PCST calls, a factor of 8.98 using $O(n^3(n+\log C) \log n)$ PCST calls, or a factor of $7.18+\epsilon$ using $n^{O(1/\epsilon)}\log C$ PCST calls, via the $k$-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here $n$ denotes the number of nodes in the instance, and $C$ is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in $O(n^2)$ time, the overall running time of our algorithm is $O(n^3 \log n)$. We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only $O(\log^2 n)$ PCST calls, and derandomize it to obtain a deterministic algorithm with factor $7.18+\epsilon$, using $O(\frac{1}{\epsilon} \log^2 n)$ PCST calls. The basic idea for our improvement is that we do not treat the $k$-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate $k$-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate $k$-MSTs for all values of $k$, even though we have them only for some values of $k$ that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.