Recently, O. Svensson and V. Traub provided the first proof of the polynomial-time approximability with fixed ratios for the Asymmetric Traveling Salesman Problem (ATSP). Just as the famous Christofides—Serdyukov algorithm for the symmetric routing problems, this breakthrough result, applied as a "black box", has opened an opportunity for developing the first polynomial-time approximation algorithms with constant ratios 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 about 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 a polynomial-time approximation with constant ratio $\max\{22+\varepsilon,4+k\}$ for arbitrary $\varepsilon>0$.
Keywords: cycle cover of a graph, asymmetric traveling salesman problem, fixed ratio approximation algorithm
Received August 4, 2023
Revised August 18, 2023
Accepted August 21, 2023
Funding Agency: This work was supported by the Russian Science Foundation (project no. 22-21-00672).
Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: mkhachay@imm.uran.ru
Ekaterina Dmitrievna Neznakhina, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: eneznakhina@yandex.ru
Kseniya Valer’evna Ryzhenko, doctoral student, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: kseniarizhenko@gmail.com
REFERENCES
1. Gimadi E.Kh., Khachai M.Yu. Ekstremal’nye zadachi na mnozhestvakh perestanovok [Extremal problems on sets of permutations]. Yekaterinburg: UMC UPI Publ., 2016, 220 p. ISBN: 978-5-8295-0497-7 .
2. Sahni S., Gonzales T. P-complete approximation problems. Journal of the ACM, 1976, vol. 23, pp. 555–565.
3. Bläser Markus, Siebert Bodo. Computing cycle covers without short cycles. In: Algorithms — ESA 2001, ed. F. Meyer auf der Heide, Ser. Lecture Notes in Computer Science, vol. 2161, Berlin; Heidelberg: Springer-Verlag, 2001, pp. 368–379. doi: 10.1007/3-540-44676-1_31
4. Bläser Markus, Shankar Ram L., Sviridenko Maxim. Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. Operations Research Letters, 2009, vol. 37, no. 3, pp. 176–180. doi: 10.1016/j.orl.2009.01.011
5. Manthey Bodo. On approximating restricted cycle covers. SIAM Journal on Computing, 2008, vol. 38, no. 1, pp. 181–206. doi: 10.1137/060676003
6. Manthey Bodo. Minimum-weight cycle covers and their approximability. Discrete Appl. Math., 2009, vol. 157, no. 7, pp. 1470–1480. doi: 10.1016/j.dam.2008.10.005
7. Khachai M.Yu., Neznakhina E.D. Approximability of the problem about a minimum-weight cycle cover of a graph. Dokl. Math., 2015, vol. 91, pp. 240–245. doi: 10.1134/S1064562415020313
8. Khachay M., Neznakhina K. Approximability of the Minimum-Weight k-Size Cycle Cover Problem. J. Global Optim., 2016, vol. 66, no. 1, pp. 65–82.
9. Neznakhina E.D. PTAS for Min-k-SCCP in Euclidean space of arbitrary fixed dimension. Proc. Steklov Inst. Math. Suppl., 2016, vol. 295, suppl. 1, pp. S120–S130. doi: 10.1134/S0081543816090133
10. Gimadi E.Kh., Rykov I.A. Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles. Proc. Steklov Inst. Math. Suppl., 2016, vol. 295, suppl. 1., pp. S57–S67. doi: 10.1134/S0081543816090078
11. Gimadi E.Kh., Rykov I.A. On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math., 2016, vol. 93, pp. 117–120. doi: 10.1134/S1064562416010233
12. Christofides N. Worst-case analysis of a new heuristic for the Traveling Salesman Problem. In: Proceedings of a Symposium on New Directions and Recent Results in Algorithms and Complexity, ed. J. F. Traub. NY; San Francisco; London: Acad. Press., 1976, p. 441.
13. Serdyukov A.I. Some extremal bypasses in graphs. Upravliaemie Systemy, 1978, iss. 17, pp. 76–79 (in Russian).
14. Wolsey Laurence A. Heuristic analysis, linear programming and branch and bound. In: Combinatorial Optimization II, ed. V.J. Rayward-Smith, Berlin, Heidelberg: Springer, 1980, p. 121–134.
15. Asadpour Arash, Goemans Michel X., Mdry Aleksander, Gharan Shayan Oveis, Saberi Amin. An O(log n/loglog n)-approximation algorithm for the asymmetric traveling salesman problem. Operations Research, 2017, vol. 65, no. 4, pp. 1043–1061. doi: 10.1287/opre.2017.1603
16. Svensson Ola, Tarnawski Jakub, and Végh László A. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. J. ACM, 2020, vol. 67, no. 6. doi: 10.1145/3424306
17. Traub Vera and Vygen Jens. An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM J. Comp., 2022, vol. 51, no. 1, pp. 139–173. doi: 10.1137/20M1339313
18. Khachay M.Yu., Neznakhina E.D., Ryzhenko K.V. Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem. Proc. Steklov Inst. Math., 2022, vol. 319, suppl. 1, pp. S140–S155. doi: 10.1134/S0081543822060128
19. Rizhenko Ksenia, Neznakhina Katherine, Khachay Michael. Fixed ratio polynomial time approximation algorithm for the prize-collecting asymmetric traveling salesman problem. Ural Math. J., 2023, vol. 9, no. 1, pp. 135–146. doi: 10.15826/umj.2023.1.012
20. Grötschel M., Lovász L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1981, vol. 1, no. 2, pp. 169–197. doi: 10.1007/BF02579273
21. Karzanov Alexander V. How to tidy up a symmetric set-system by use of uncrossing operations. Theoretical Computer Science, 1996, vol. 157, no. 2, pp. 215–225. doi: 10.1016/0304-3975(95)00160-3
22. Frieze A.M., Galbiati G., Maffioli F. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 1982, vol. 12, no. 1, pp. 23–39. doi: 10.1002/net.3230120103
23. Schrijver A. Combinatorial optimization — polyhedra and efficiency. NY: Springer, 2003. 1189 p.
Cite this article as: M.Yu. Khachai, E.D. Neznakhina, K.V. Ryzhenko. Polynomial approximability of the asymmetric problem of covering a graph by a bounded number of cycles. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 261–273; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S121–S132.
