DIMACS Theory Seminar


Approximating the Minimum Latency Problem


Michel Goemans


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Friday, April 12, 1996


The minimum latency problem is the problem of finding a tour on a set of points that minimizes the average distance traveled to any point. This problem is NP-complete, and appears to be much more difficult than the related and famous traveling salesman problem. Blum, Chalasani, Coppersmith, Pulleyblank, Raghavan, and Sudan gave the first constant-factor approximation algorithm for the problem, obtaining an approximation ratio of 144. In this talk, I will describe improved approximation algorithms; our performance guarantees are $21.546...=6\gamma$ for general metric spaces and $\gamma$ for the problem on trees, where $\gamma$ is the unique root of $3.581... =\gamma\ln(\gamma)=\gamma+1$. One of the key improvements is based on relating the performance guarantee of our algorithm to the length of a shortest path in a specially weighted graph.

This is based on joint work with Jon Kleinberg.

Document last modified on April 11, 1996