Geodesic
Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem
Ural mathematical journal, Tome 9 (2023) no. 1, pp. 135-146

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Prize-Collecting Traveling Salesman Problem, triangle inequality, approximation algorithm, fixed approximation ratio. 
@article{UMJ_2023_9_1_a11,
     author = {Ksenia Ryzhenko and Katherine Neznakhina and Michael Khachay},
     title = {Fixed ratio polynomial time approximation algorithm for the {Prize-Collecting} {Asymmetric} {Traveling} {Salesman} {Problem}},
     journal = {Ural mathematical journal},
     pages = {135--146},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2023_9_1_a11/}
}
TY  - JOUR
AU  - Ksenia Ryzhenko
AU  - Katherine Neznakhina
AU  - Michael Khachay
TI  - Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem
JO  - Ural mathematical journal
PY  - 2023
SP  - 135
EP  - 146
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UMJ_2023_9_1_a11/
LA  - en
ID  - UMJ_2023_9_1_a11
ER  - 
%0 Journal Article
%A Ksenia Ryzhenko
%A Katherine Neznakhina
%A Michael Khachay
%T Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem
%J Ural mathematical journal
%D 2023
%P 135-146
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UMJ_2023_9_1_a11/
%G en
%F UMJ_2023_9_1_a11
Ksenia Ryzhenko; Katherine Neznakhina; Michael Khachay. Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem. Ural mathematical journal, Tome 9 (2023) no. 1, pp. 135-146. http://geodesic.mathdoc.fr/item/UMJ_2023_9_1_a11/