Labeled Traveling Salesman Problems: Complexity and approximation

We consider labeled Traveling Salesman Problems, defined upon a complete graph of nn 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 n1−ϵn1−ϵ for any fixed ϵ>0ϵ>0. When every color appears in the graph at most rr times and rr is an increasing function of nn, the problem is shown not to be approximable within factor O(r1−ϵ)O(r1−ϵ). For fixed constant rr we analyze a polynomial-time (r+Hr)/2(r+Hr)/2-approximation algorithm, where HrHr is the rrth harmonic number, and prove APX-hardness for r=2r=2. For all of the analyzed algorithms we exhibit tightness of their analysis by provision of appropriate worst-case instances.