  We present approximation algorithms for almost all variants of the
multi-criteria traveling salesman problem (TSP).
  First, we devise randomized approximation algorithms for multi-criteria
maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP,
where the edge weights have to be symmetric, we devise an algorithm with an
approximation ratio of 2/3 - eps. For multi-criteria Max-ATSP, where the edge
weights may be asymmetric, we present an algorithm with a ratio of 1/2 - eps.
Our algorithms work for any fixed number k of objectives. Furthermore, we
present a deterministic algorithm for bi-criteria Max-STSP that achieves an
approximation ratio of 7/27.
  Finally, we present a randomized approximation algorithm for the asymmetric
multi-criteria minimum TSP with triangle inequality Min-ATSP. This algorithm
achieves a ratio of log n + eps.
