# Computational Complexity - Research Seminar

## Bodo Manthey: *Multi-Criteria TSP: Min and Max Combined*

July 2, 2009, 10:15 a.m.

E 1 3, Room 415

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized.

For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3-ε, 4+ε) approximate Pareto curves. (The first parameter is the approximation ratio for the max, and the second parameter is the ratio for the min objectives.)

For the asymmetric multi-criteria TSP (ATSP), we present an algorithm that computes (1/2-ε, log_{2} n +ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria TSP with only max objectives.