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 $\gamma$-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of $\min\left\{1+\gamma,{2\gamma^2\over 2\gamma^2-2\gamma +1}\right\} + \varepsilon$ and a randomized approximation algorithm that achieves a ratio of ${2\gamma^3 + 2\gamma^2\over 3\gamma^2-2\gamma +1} + \varepsilon$. In particular, we obtain a $2+\varepsilon$ approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with $\gamma$-triangle inequality ratio ${1\gamma\over 1+3\gamma-4\gamma^2}+ \varepsilon$ ), asymmetric TSP (ATSP) with $\gamma$-triangle inequality (ratio ${1\over 2} + {\gamma^3\over 1-3\gamma^2}+ \varepsilon$ ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).