Standard

Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles. / Khachai, M.; Neznakhina, E.; Ryzhenko, K.
в: Proceedings of the Steklov Institute of Mathematics, Том 323, № S1, 01.12.2023, стр. S121-S132.

Результаты исследований: Вклад в журналСтатьяРецензирование

Harvard

Khachai, M, Neznakhina, E & Ryzhenko, K 2023, 'Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles', Proceedings of the Steklov Institute of Mathematics, Том. 323, № S1, стр. S121-S132. https://doi.org/10.1134/S008154382306010X

APA

Vancouver

Khachai M, Neznakhina E, Ryzhenko K. Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles. Proceedings of the Steklov Institute of Mathematics. 2023 дек. 1;323(S1):S121-S132. doi: 10.1134/S008154382306010X

Author

Khachai, M. ; Neznakhina, E. ; Ryzhenko, K. / Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles. в: Proceedings of the Steklov Institute of Mathematics. 2023 ; Том 323, № S1. стр. S121-S132.

BibTeX

@article{492ce2fa805a4870a212b0198f851581,
title = "Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles",
abstract = "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.",
author = "M. Khachai and E. Neznakhina and K. Ryzhenko",
note = "This research was supported by the Russian Science Foundation (project no. 22-21-00672, https://rscf.ru/project/22-21-00672/).",
year = "2023",
month = dec,
day = "1",
doi = "10.1134/S008154382306010X",
language = "English",
volume = "323",
pages = "S121--S132",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Pleiades Publishing",
number = "S1",

}

RIS

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