On approximating multicriteria TSP

摘要

We present approximation algorithms for almost all variants of the multicriteria traveling salesman problem (TSP). First, we devise randomized approximation algorithms for multicriteria maximum traveling salesman problems (Max-TSP). For multicriteria Max-STSP where the edge weights have to be symmetric, we devise an algorithm with an approximation ratio of 2/3 - ε. For multicriteria Max-ATSP where the edge weights may be asymmetric, we present an algorithm with a ratio of 1/2 - ε. Our algorithms work for any fixed number k of objectives. Furthermore, we present a deterministic algorithm for bicriteria Max-STSP that achieves an approximation ratio of 7/27. Finally, we present a randomized approximation algorithm for the asymmetric multicriteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of logn+ ε.