(Non)-Approximability for the Multi-criteria TSP(1,2)

摘要

Many papers deal with the approximability of multi-criteria optimization problems but only a small number of non-approximability results, which rely on NP-hardness, exist in the literature. In this paper, we provide a new way of proving non-approximability results which relies on the existence of a small size good approximating set (i.e. it holds even in the unlikely event of P = NP). This method may be used for several problems but here we illustrate it for a multi-criteria version of the traveling salesman problem with distances one and two (TSP(1, 2)). Following the article of Angel et al. (FCT 2003) who presented an approximation algorithm for the bi-criteria TSP(1,2), we extend and improve the result to any number k of criteria.