Even in the single criterion case, the classic traveling salesman problem (TSP) is known to be nondeterministic polynomial time (NP) hard. For efficiency in solving TSP, one seeks good enough approximations rather than the optimum. In contrast to tractable approximation algorithms for solving single objective TSPs, this paper provides both deterministic and randomized schemes in polynomial time, to solve multi-criteria &ggr;−TSPs and &Dgr;(&ggr;)−TSPs, with proven approximation ratios.

Specifically, the authors derive a deterministic polynomial-time algorithm that computes (2 + &egr;)-approximate Pareto curves for an undirected &ggr;−TSP generalized Christofides algorithm to a randomized approximation algorithm for multi-criteria &Dgr;(&ggr;)−TSP. They consider cycle covers in designing approximation algorithms for TSP, and declare the existence of a fully polynomial-time randomized approximation scheme (FPRAS) to approximate Pareto curves of multi-criteria cycle covers. The approximation ratio for &Dgr;(&ggr;)−TSP is for undirected TSP with &ggr; < 1, and for directed TSP with .

The theoretic results, and the approaches to obtain them, certainly make this paper appealing to researchers in algorithms and computational theory. Those who work on finding approximated solutions in solving real multi-criteria TSPs should also benefit, especially since the authors claim that their proposed schemes work for any fixed number of objective functions for &ggr;−TSPs and &Dgr;(&ggr;)−TSPs.