We propose a generalized definition for the multi-objective traveling salesman problem which uses multigraphs and which allows multiple visits of cities. The definition has two benefits: it captures typical real-world scenarios and it contains the conventional definition (componentwise metric cost function) as a special case.

We provide approximation algorithms for this general version of the two-objective traveling salesman problem (2-TSP). At the same time, with these algorithms we improve the best known approximations for the conventional case. For 2-TSP we obtain a deterministic 2-approximation, a randomized $(3/2+\epsilon, 2)$-approximation, and a randomized $(3/2, 2+\epsilon)$-approximation. Moreover, we construct similar algorithms for two-objective traveling salesman path problems.

Further we present arguments that indicate the hardness of improving our randomized approximation algorithms in the sense that such improvements force us to improve the best known approximations for TSP, TSPPs, and TSPPst (Christofides 1976, Hoogeveen 1991). In this way, we can narrow down the approximation ratios for 2-TSP that could be within reach, i.e., that will not immediately improve well-studied approximations. This leads to the question of whether 2-TSP has an $(\alpha, \beta)$-approximation where $5/3 \leq \alpha, \beta < 2$.

This major revision extends the results of the original technical report to a more general model of multi-objective TSP.

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria traveling salesman path problems 2-TSPP, 2-TSPPs, and 2-TSPPst. We further provide arguments that indicate the hardness of improving our randomized approximation algorithms in the sense that such improvements force us to improve the best known approximations for TSP, TSPPs, and TSPPst (Christofides 1976, Hoogeveen 1991).

A particular interesting situation emerges for 2-TSP: Because of possible trade-offs between the approximation ratios in the first and in the second component, there could exist randomized approximation algorithms that are incomparable to our algorithms. For these we can narrow down the approximation ratios that could be within reach, i.e., that will not force us to improve the well-studied approximations by Christofides and Hoogeveen. This leads to the question of whether 2-TSP has an $(\alpha, \beta)$-approximation where $5/3 \leq \alpha, \beta < 2$.