Labeled Traveling Salesman Problems: Complexity and approximation
Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010), Labeled Traveling Salesman Problems: Complexity and approximation, Discrete Optimization, 7, 1-2, p. 74-85. http://dx.doi.org/10.1016/j.disopt.2010.02.003
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Optimization
MetadataShow full item record
Abstract (EN)We consider labeled Traveling Salesman Problems, defined upon a complete graph of n vertices with colored edges. The objective is to find a tour of maximum or minimum number of colors. We derive results regarding hardness of approximation and analyze approximation algorithms, for both versions of the problem. For the maximization version we give a View the MathML source-approximation algorithm based on local improvements and show that the problem is APX-hard. For the minimization version, we show that it is not approximable within n1−ϵ for any fixed ϵ>0. When every color appears in the graph at most r times and r is an increasing function of n, the problem is shown not to be approximable within factor O(r1−ϵ). For fixed constant r we analyze a polynomial-time (r+Hr)/2-approximation algorithm, where Hr is the rth harmonic number, and prove APX-hardness for r=2. For all of the analyzed algorithms we exhibit tightness of their analysis by provision of appropriate worst-case instances.
Subjects / KeywordsApproximation algorithms; Hamilton tour; Traveling Salesman Problem; Edge-colored graphs; Complexity
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié