An Improved 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-MST problem which is called as a black box for each value of k. 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+e while using nO(1/e) PCST calls (via a k-MST algorithm of Arora and Karakostas). In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine 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. This allows us to take advantage of some special situations in which the PCST subroutine delivers a k-MST with a performance guarantee of 2. 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-MST’s 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.

By: Aaron Archer, Asaf Levin, David P. Williamson

Published in: RJ10294 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .