Back to Search
Start Over
A FASTER, BETTER APPROXIMATION ALGORITHM FOR THE MINIMUM LATENCY PROBLEM.
- Source :
-
SIAM Journal on Computing . 2007, Vol. 37 Issue 5, p1472-1498. 27p. 1 Diagram, 2 Charts, 1 Graph. - Publication Year :
- 2007
-
Abstract
- 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³ (n + log C) log n) PCST calls, or a factor of 7.18 + ϵ using nO(1/ϵ) 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²) time, the overall running time of our algorithm is O(n³ 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² n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + ϵ, using O( 1/ϵ log² 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 37
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 85251971
- Full Text :
- https://doi.org/10.1137/07068151X