FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM

Abstract

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 α-approximation algorithm for the Asymmetric Traveling Salesman Problem induces an (α + 1)-approximation for the problem in question. In particular, using the recent (22 + ε)-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 + ε)-approximate solutions for the problem.