Geodesic
Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 3, pp. 241-258

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

For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the $(22+\varepsilon)$-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.
Keywords: asymmetric traveling salesman problem, constant-factor approximation algorithm, polynomial-time reduction, Steiner cycle problem, generalized traveling salesman problem, prize collecting traveling salesman problem, vehicle routing problem. 
@article{TIMM_2022_28_3_a17,
     author = {M. Yu. Khachay and E. D. Neznakhina and K. V. Ryzhenko},
     title = {Constant-Factor {Approximation} {Algorithms} for a {Series} of {Combinatorial} {Routing} {Problems} {Based} on the {Reduction} to the {Asymmetric} {Traveling} {Salesman} {Problem}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {241--258},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_3_a17/}
}
TY  - JOUR
AU  - M. Yu. Khachay
AU  - E. D. Neznakhina
AU  - K. V. Ryzhenko
TI  - Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 241
EP  - 258
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_3_a17/
LA  - ru
ID  - TIMM_2022_28_3_a17
ER  - 
%0 Journal Article
%A M. Yu. Khachay
%A E. D. Neznakhina
%A K. V. Ryzhenko
%T Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 241-258
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_3_a17/
%G ru
%F TIMM_2022_28_3_a17
M. Yu. Khachay; E. D. Neznakhina; K. V. Ryzhenko. Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 3, pp. 241-258. http://geodesic.mathdoc.fr/item/TIMM_2022_28_3_a17/