Geodesic
Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 261-273

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

Recently, O. Svensson and V. Traub have provided the first proof of the polynomial-time approximability of the asymmetric traveling salesman problem (ATSP) in the class of constant-factor approximation algorithms. Just as the famous Christofides–Serdyukov algorithm for the symmetric routing problems, these breakthrough results, applied as a “black box,” have opened an opportunity for developing the first constant-factor polynomial-time approximation algorithms for several related combinatorial problems. At the same time, problems have been revealed in which this simple approach, based on reducing a given instance to one or more auxiliary ATSP instances, does not succeed. In the present paper, we extend the Svensson–Traub approach to the wider class of problems related to finding a minimum-weight cycle cover of an edge-weighted directed graph with an additional constraint on the number of cycles. In particular, it is shown for the first time that the minimum weight cycle cover problem with at most $k$ cycles admits polynomial-time approximation with constant factor $\max\{22+\varepsilon,4+k\}$ for arbitrary $\varepsilon>0$.
Keywords: cycle cover of a graph, asymmetric traveling salesman problem, constant-factor approximation algorithm. 
@article{TIMM_2023_29_3_a15,
     author = {M. Yu. Khachay and E. D. Neznakhina and K. V. Ryzhenko},
     title = {Polynomial-Time {Approximability} of the {Asymmetric} {Problem} of {Covering} a {Graph} by a {Bounded} {Number} of {Cycles}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {261--273},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a15/}
}
TY  - JOUR
AU  - M. Yu. Khachay
AU  - E. D. Neznakhina
AU  - K. V. Ryzhenko
TI  - Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2023
SP  - 261
EP  - 273
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a15/
LA  - ru
ID  - TIMM_2023_29_3_a15
ER  - 
%0 Journal Article
%A M. Yu. Khachay
%A E. D. Neznakhina
%A K. V. Ryzhenko
%T Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles
%J Trudy Instituta matematiki i mehaniki
%D 2023
%P 261-273
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a15/
%G ru
%F TIMM_2023_29_3_a15
M. Yu. Khachay; E. D. Neznakhina; K. V. Ryzhenko. Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 261-273. http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a15/