Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem

We develop the first fixed-ratio approximation algorithm for the well-known Prize-Collecting Asymmetric Traveling Salesman Problem, which has numerous valuable applications in operations research. An instance of this problem is given by a complete node- and edge-weighted digraph $G$. Each node of the graph $G$ can either be visited by the resulting route or skipped, for some penalty, while the arcs of $G$ are weighted by non-negative transportation costs that fulfill the triangle inequality constraint. The goal is to find a closed walk that minimizes the total transportation costs augmented by the accumulated penalties. We show that an arbitrary $\alpha$-approximation algorithm for the Asymmetric Traveling Salesman Problem induces an $(\alpha+1)$-approximation for the problem in question. In particular, using the recent $(22+\varepsilon)$-approximation algorithm of V. Traub and J. Vygen that improves the seminal result of O. Svensson, J. Tarnavski, and L. Végh, we obtain $(23+\varepsilon)$-approximate solutions for the problem.