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

International audienceMany 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