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.
Document last modified on April 11, 1996