Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Bodo Manthey: On Approximating Multi-Criteria TSP

Jan. 22, 2009, 10:15 a.m.
E 1 3, Room 415

In many optimization problems, there is more than one objective to be optimized. In this case, there is no natural notion of a best choice. Instead, the goal is to compute a so-called Pareto curve of solutions, which is the set of all solutions that can be considered optimal. Since computing Pareto curves is very often intractable, one has to be content with approximations to them.

We present approximation algorithms for several variants of the multi-criteria traveling salesman problem (TSP), whose approximation performances are independent of the number k of criteria and come close to the approximation ratios obtained for TSP with a single objective function.

First, we present a randomized approximation ratio for multi-criteria Min-ATSP with an approximation ratio of log n + ε, where ε can be made arbitrarily small. Second, we present a randomized 1/2 - ε approximation algorithm for multi-criteria Max-ATSP. This algorithms can be turned into a 2/3 - ε approximation for multi-criteria Max-STSP. Finally, we devise a deterministic 1/4 approximation algorithm for bi-criteria Max-STSP.