Bodo Manthey — Christofides' Algorithm for Multi-Criteria TSP
Time: | Wednesday, September 29, 2010, 12:45-13:30 |
Location: | Room 101, Citadel |
The traveling salesman problem (TSP) is the following optimization problem:
Given an undirected complete graph with edge lengths, which fulfil the
triangle inequality, the goal is to compute a Hamiltonian cycle of minimum length.
We consider the following multi-objective variant of the TSP: We are given k different edge length functions
d1, d2, ..., dk and k budgets
b1, b2, ..., bk.
Now, if there exists a Hamiltonian cycle H with di(H)
≤ bi for all i,
find a Hamiltonian cycle H' with di(H')
≤ α bi for all i. This means that we exceed each budget by
at most a factor of α.
Christofides' algorithm does this task
with α= 3/2 for the special case k=1.
Unfortunately, for k≥2, Christofides' algorithm seems to achieve only roughly α = 2.
We conjecture that it is possible to beat α=2, at least for k=2.