## 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
*d _{1}*,

*d*, ...,

_{2}*d*and

_{k}*k*budgets

*b*,

_{1}*b*, ...,

_{2}*b*. Now, if there exists a Hamiltonian cycle

_{k}*H*with

*d*(

_{i}*H*) ≤

*b*for all

_{i}*i*, find a Hamiltonian cycle

*H*' with

*d*(

_{i}*H*') ≤ α

*b*for all

_{i}*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.