(Non)-Approximability for the multi-criteria TSP(1,2)
Monnot, Jérôme; Gourvès, Laurent; Bampis, Evripidis; Angel, Eric (2005), (Non)-Approximability for the multi-criteria TSP(1,2), in Reischuk, Rüdiger; Liskiewicz, Maciej, Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings, Springer : Berlin, p. 329-340. http://dx.doi.org/10.1007/11537311_29
TypeCommunication / Conférence
External document linkhttp://hal.archives-ouvertes.fr/hal-00115511/en/
Conference titleFundamentals of Computation Theory (FCT 2005)
Book titleFundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings
Book authorReischuk, Rüdiger; Liskiewicz, Maciej
Series titleLecture Notes in Computer Science
Number of pages576
MetadataShow full item record
Abstract (EN)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 foseveral problems but here we illustrate it for a multi-criteria version of the traveling salesman problem with distances one and two (T SP (1, 2)). Following the article of Angel et al. (FCT 2003) who presented an approximation algorithm for the bi-criteria T SP (1, 2), we extend and improve the result to any number k of criteria.
Subjects / Keywordsoptimization problems; multi-criteria; approximability of multi-criteria; approximation algorithm; NP-complete; traveling salesman problem
Showing items related by title and author.