Approximating the asymmetric profitable tour (Q1758879)

Summary: We study the version of the asymmetric prize collecting travelling 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 [\textit{M. Dell'Amico} et al., Int. Trans. Oper. Res. 2, No. 3, 297--308 (1995; Zbl 0860.90121)], the authors defined it as the profitable tour problem (PTP). We present an \((1 + \lceil \log(n)\rceil )\)-approximation algorithm for the asymmetric PTP, where \(n\) denotes the number of vertices. The algorithm is based on a heuristic for the asymmetric travelling salesman problem by \textit{A. M. Frieze} et al. [Networks 12, 23--39 (1982; Zbl 0478.90070)], 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 algorithm for the symmetric PTP by \textit{D. Bienstock} et al. [Math. Program. 59, No. 3 (A), 413--420 (1993; Zbl 0793.90089)].