Результаты исследований: Вклад в журнал › Статья › Рецензирование
Результаты исследований: Вклад в журнал › Статья › Рецензирование
}
TY - JOUR
T1 - Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles
AU - Khachai, M.
AU - Neznakhina, E.
AU - Ryzhenko, K.
N1 - This research was supported by the Russian Science Foundation (project no. 22-21-00672, https://rscf.ru/project/22-21-00672/).
PY - 2023/12/1
Y1 - 2023/12/1
N2 - 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 cycles admits polynomial-time approximation with constant factor for arbitrary.
AB - 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 cycles admits polynomial-time approximation with constant factor for arbitrary.
UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85185149754
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=001163182700010
U2 - 10.1134/S008154382306010X
DO - 10.1134/S008154382306010X
M3 - Article
VL - 323
SP - S121-S132
JO - Proceedings of the Steklov Institute of Mathematics
JF - Proceedings of the Steklov Institute of Mathematics
SN - 0081-5438
IS - S1
ER -
ID: 53790383