Approximation algorithms for multi-criteria traveling salesman problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ–triangle inequality. For this problem, we present a deterministic polynomial–time algorithm that achieves an approximation ratio of: $\text{min}\left\{1+\gamma \text{,}\frac{2{\gamma }^2}{2{\gamma }^2-2\gamma +1}\right\}+ϵ$ and a randomized approximation algorithm that achieves a ratio of $\frac{2{\gamma }^3+2{\gamma }^2}{3{\gamma }^2-2\gamma +1}+ϵ$ . In particular, we obtain a 2+ϵ approximation for the multi-criteria metric STSP.