Complexity and approximation for Traveling Salesman Problems with profits

In TSP with profits we have to find an optimal tour and a set of customers satisfying a specific constraint. In this paper we analyze three different variants of TSP with profits that are NP-hard in general. We study their computational complexity on special structures of the underlying graph, both in the case with and without service times to the customers. We present polynomial algorithms for the polynomially solvable cases and fully polynomial time approximation schemes (FPTAS) for some NP-hard cases.