CS 789 THEORY SEMINAR [home]

Speaker:  Aaron Archer
Affiliation: Computer Science, Cornell University
Date: Monday, November 11, 2002
Title: "Faster Approximation Algorithms for the Minimum Latency Problem" 

Abstract:

We consider the minimum latency problem (MLP), a variant on the traveling salesman problem (TSP) that is sometimes called the traveling repairman problem or the deliveryman problem. Instead of minimizing the total travel time as in the TSP, the objective in the MLP is to  minimize the average arrival time at all the customer locations. Thus, the MLP objective is client-oriented, whereas the TSP is server-oriented. We give a 7.18-approximation algorithm for the MLP that requires only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson, yielding an overall running time of O(n^3 log n). A previous algorithm of Goemans and Kleinberg requires an approximation algorithm for the k-MST problem (the problem of finding a minimum cost tree spanning k vertices), 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(n^2 log n) PCST calls (via a k-MST algorithm of Garg), or a performance guarantee of 7.18 + eps while using n^O(1/eps) PCST calls (via a k-MST algorithm of Arora and Karakostas). Thus, we improve both the running time and approximation guarantee of these algorithms.

The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. The PCST subroutine returns 2-approximate k-MST's for some values of k that we cannot control. We show how to use this small collection of trees in the algorithm of Goemans and Kleinberg to achieve the same approximation ratio that would be obtained if we had access to 2-approximate k-MST's for all values of k.

This is joint work with David Williamson and Asaf Levin.