Approximating the asymmetric profitable tour

We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In \cite{Amico}, the authors defined it as the \textit{Profitable Tour Problem} (PTP). We present an $(1+\log(n))$-approximation algorithm for the asymmetric PTP with $n$ is the vertex number. The algorithm that is based on Frieze et al.’s heuristic for the asymmetric traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers (feasible solution for the original problem), represents a directed version of the Bienstock et al.’s \cite{Bienstock} algorithm for the symmetric PTP.

Article

Download

View PDF