DIMACS Theory Seminar


Title:

Approximating the Minimum Latency Problem

Speaker:

Michel Goemans
MIT

Place:

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

Time:

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

Abstract:

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.


dimacs-www@dimacs.rutgers.edu
Document last modified on April 11, 1996