Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

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-ε, log2 n +ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria TSP with only max objectives.