Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles

M. Yu. Khachay ; E. D. Neznakhina ; K. V. Ryzhenko

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 261-273

Résumé

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$.

Détail

Keywords: cycle cover of a graph, asymmetric traveling salesman problem, constant-factor approximation algorithm.

Bibliographie

[1] Gimadi E.Kh., Khachai M.Yu., Ekstremalnye zadachi na mnozhestvakh perestanovok, UMTs UPI, Ekaterinburg, 2016, 220 pp.

[2] Sahni S., Gonzales T., “$P$-complete approximation problems”, Journal of the ACM, 23 (1976), 555–565 | DOI | MR | Zbl

[3] Bläser Markus, Siebert Bodo, “Computing cycle covers without short cycles”, Algorithms — ESA 2001, Lecture Notes in Computer Science, 2161, ed. F. Meyer auf der Heide, Springer-Verlag, Berlin; Heidelberg, 2001, 368–379 | DOI | MR

[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, 37:3 (2009), 176–180 | DOI | MR

[5] Manthey Bodo, “On approximating restricted cycle covers”, SIAM Journal on Computing, 38:1 (2008), 181–206 | DOI | MR | Zbl

[6] Manthey Bodo, “Minimum-weight cycle covers and their approximability”, Discrete Appl. Math., 157:7 (2009), 1470–1480 | DOI | MR | Zbl

[7] Khachai M.Yu., Neznakhina E.D., “Approximability of the problem about a minimum-weight cycle cover of a graph”, Dokl. Math., 91 (2015), 240–245 | DOI | MR | Zbl

[8] Khachay M., Neznakhina K., “Approximability of the Minimum-Weight $k$-Size Cycle Cover Problem”, J. Global Optim., 66:1 (2016), 65–82 | DOI | MR | Zbl

[9] E. D. Neznakhina, “PTAS dlya zadachi Min-$k$-SCCP v evklidovom prostranstve proizvolnoi fiksirovannoi razmernosti”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 268–278

[10] E. Kh. Gimadi, I. A. Rykov, “Asimptoticheski tochnyi podkhod k priblizhennomu resheniyu nekotorykh zadach pokrytiya grafa”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 89–99

[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., 93 (2016), 117–120 | DOI | MR | Zbl

[12] Christofides N., “Worst-case analysis of a new heuristic for the Traveling Salesman Problem”, Proceedings of a Symposium on New Directions and Recent Results in Algorithms and Complexity, ed. J. F. Traub, Acad. Press, NY; San Francisco; London, 1976, 441

[13] Serdyukov A.I., “O nekotorykh ekstremalnykh obkhodakh v grafakh”, Upravlyaemye sistemy, 1978, no. 17, 76–79 | Zbl

[14] Wolsey Laurence A., “Heuristic analysis, linear programming and branch and bound”, Combinatorial Optimization II, ed. V.J. Rayward-Smith, Springer, Berlin, Heidelberg, 1980, 121–134 | DOI | MR

[15] Asadpour Arash, Goemans Michel X., Madry Aleksander, Gharan Shayan Oveis, Saberi Amin, “An $O(\log n/\log\log n)$-approximation algorithm for the asymmetric traveling salesman problem”, Operations Research, 65:4 (2017), 1043–1061 | DOI | MR | Zbl

[16] Svensson Ola, Tarnawski Jakub, and Végh László A., “A constant-factor approximation algorithm for the asymmetric traveling salesman problem”, J. ACM, 67:6 (2020) | DOI | MR | Zbl

[17] Traub Vera and Vygen Jens, “An improved approximation algorithm for the asymmetric traveling salesman problem”, SIAM J. Comp., 51:1 (2022), 139–173 | DOI | MR

[18] M. Yu. Khachai, E. D. Neznakhina, K. V. Ryzhenko., “Priblizhennye algoritmy s postoyannoi tochnostyu dlya serii marshrutnykh kombinatornykh zadach, osnovannye na svedenii k asimmetrichnoi zadache kommivoyazhera”, Tr. In-ta matematiki i mekhaniki UrO RAN, 29:3 (2022), 241–258 | DOI

[19] Rizhenko Ksenia, Neznakhina Katherine, Khachay Michael, “Fixed ratio polynomial time approximation algorithm for the prize-collecting asymmetric traveling salesman problem”, Ural Math. J., 9:1 (2023), 135–146 | DOI | MR

[20] Grötschel M., Lovász L., Schrijver A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1:2 (1981), 169–197 | DOI | MR | Zbl

[21] Karzanov Alexander V., “How to tidy up a symmetric set-system by use of uncrossing operations”, Theoretical Computer Science, 157:2 (1996), 215–225 | DOI | MR | Zbl

[22] Frieze A.M., Galbiati G., Maffioli F., “On the worst-case performance of some algorithms for the asymmetric traveling salesman problem”, Networks, 12:1 (1982), 23–39 | DOI | MR | Zbl

[23] Schrijver A., Combinatorial optimization — polyhedra and efficiency, Springer, NY, 2003, 1189 pp. | MR | Zbl