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.