Deterministic algorithms for multi-criteria Max-TSP

We present deterministic approximation algorithms for the multi-criteria maximum traveling salesman problem (Max-TSP). Our algorithms are faster and simpler than the existing randomized algorithms.We devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k−ε1/2k−ε and 1/(4k−2)−ε1/(4k−2)−ε, respectively, where kk is the number of objective functions. For two objective functions, we obtain ratios of 3/8−ε3/8−ε and 1/4−ε1/4−ε for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.