Paper Info
Title
Labeled Traveling Salesman Problems: Complexity and approximation
Abstract
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 12-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 n^1^-^@e for any fixed @e0. 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(r^1^-^@e). For fixed constant r we analyze a polynomial-time (r+H"r)/2-approximation algorithm, where H"r 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.
Year
DOI
Venue
2010
10.1016/j.disopt.2010.02.003
Discrete Optimization
Keywords
Field
DocType
complete graph,maximization version,12-approximation algorithm,n vertex,traveling salesman problem,approximation algorithms,minimum number,approximation algorithm,fixed constant r,r time,salesman problems,minimization version,edge-colored graphs,complexity,2-approximation algorithm,hamilton tour,edge coloring,harmonic number,hardness of approximation,polynomial time
Bottleneck traveling salesman problem,Approximation algorithm,Discrete mathematics,Complete graph,Mathematical optimization,Combinatorics,Vertex (geometry),Hardness of approximation,Harmonic number,Travelling salesman problem,Maximization,Mathematics
Journal
Volume
Issue
ISSN
7
1-2
Discrete Optimization
Citations 
PageRank 
References 
6
0.47
14
Authors
4
Name
Order
Citations
PageRank
Basile Couëtoux1182.81
Laurent Gourvès224130.97
Jérôme Monnot351255.74
Orestis A. Telelis4474.95