DMMP Seminar

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.