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 + eps, where eps can be made arbitrarily small. Second, we present a randomized 1/2 - eps approximation algorithm for multi-criteria Max-ATSP. This algorithms can be turned into a 2/3 - eps approximation for multi-criteria Max-STSP. Finally, we devise a deterministic 1/4 approximation algorithm for bi-criteria Max-STSP.