Constant-Ratio polynomial time approximation of the asymmetric minimum weight cycle cover problem with limited number of cycles

[1] A. Asadpour, M.X. Goemans, A. Madry, S.O. Gharan, and A. Saberi, An ${O}(\log/\log\log n)$-approximation algorithm for the asymmetric traveling salesman problem, Oper. Res. 65 (2017), no. 4, 1043–1061. https://doi.org/10.1287/opre.2017.1603

[2] M. Bläser, B. Manthey, and J. Sgall, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, J. Discrete Algorithms 4 (2006), no. 4, 623–632. https://doi.org/10.1016/j.jda.2005.07.004

[3] M. Bläser and B. Siebert, Computing cycle covers without short cycles, Algorithms - ESA 2001 (Berlin, Heidelberg) (F.M. auf der Heide, ed.), Springer Berlin Heidelberg, 2001, pp. 368–379.

[4] C. Bordenave, M. Gendreau, and G. Laporte, Heuristics for the mixed swapping problem, Comput. Oper. Res. 37 (2010), no. 1, 108–114. https://doi.org/10.1016/j.cor.2009.03.032

[5] L.S. Chandran and L.S. Ram, On the relationship between ATSP and the cycle cover problem, Theoret. Comput. Sci. 370 (2007), no. 1, 218–228. https://doi.org/10.1016/j.tcs.2006.10.026

[6] N. Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Management Science[s] Research Group, Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.

[7] E.K. Gimadi and I.A. Rykov, Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles, Proc. Steklov Inst. Math. 295 (2016), no. 1, 57–67. https://doi.org/10.1134/S0081543816090078

[8] B. Graf, Preemptive stacker crane problem: Extending tree-based properties and construction heuristics, European J. Oper. Res. 292 (2021), no. 2, 532–547. https://doi.org/10.1016/j.ejor.2020.10.051

[9] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), no. 2, 169–197. https://doi.org/10.1007/BF02579273

[10] M. Haimovich and A.H.G. Rinnooy Kan, Bounds and heuristics for capacitated routing problems, Math. Oper. Res. 10 (1985), no. 4, 527–542. https://doi.org/10.1287/moor.10.4.527

[11] R. Hassin and S. Rubinstein, On the complexity of the k-customer vehicle routing problem, Oper. Res. Lett. 33 (2005), no. 1, 71–76. https://doi.org/10.1016/j.orl.2004.04.003

[12] A.V. Karzanov, How to tidy up a symmetric set-system by use of uncrossing operations, Theoret. Comput. Sci. 157 (1996), no. 2, 215–225. https://doi.org/10.1016/0304-3975(95)00160-3

[13] M.Y. Khachai and E.D. Neznakhina, Approximability of the problem about a minimum-weight cycle cover of a graph, Dokl. Math. 91 (2015), no. 2, 240–245. https://doi.org/10.1134/S1064562415020313

[14] M.Y. Khachai and E.D. Neznakhina, A polynomial-time approximation scheme for the euclidean problem on a cycle cover of a graph, Proc. Steklov Inst. Math. 289 (2015), no. 1, 111–125. https://doi.org/10.1134/S0081543815050107

[15] M. Khachay and K. Neznakhina, Approximability of the minimum-weight $k$-size  cycle cover problem, J. Global Optim. 66 (2016), no. 1, 65–82. https://doi.org/10.1007/s10898-015-0391-3

[16] M.Y. Khachay, E.D. Neznakhina, and K.V. Ryzhenko, 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. 319 (2022), no. Suppl 1, S140–S155. https://doi.org/10.1134/S0081543822060128

[17] B. Manthey, Minimum-weight cycle covers and their approximability, Discrete Appl. Math. 157 (2009), no. 7, 1470–1480. https://doi.org/10.1016/j.dam.2008.10.005

[18] E.D. Neznakhina, Y.Y. Ogorodnikov, K.V. Rizhenko, and M.Y. Khachay, Approximation algorithms with constant factors for a series of asymmetric routing problems, Dokl. Math. 108 (2023), no. 3, 499–505. https://doi.org/10.1134/S1064562423701454

[19] C.H. Papadimitriou, The euclidean travelling salesman problem is NP-complete, Theoret. Comput. Sci. 4 (1977), no. 3, 237–244. https://doi.org/10.1016/0304-3975(77)90012-3

[20] K. Rizhenko, K. Neznakhina, and M. Khachay, Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem, Ural Math. J. 9 (2023), no. 1, 135–146. http://dx.doi.org/10.15826/umj.2023.1.012

[21] A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003.

[22] A.I. Serdyukov, Some extremal bypasses in graphs (in Russian), Upravlyaemye Systemy 17 (1978), 76–79.

[23] O. Svensson, J. Tarnawski, and L.A. Végh, A constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem, J. Appl. Comput. Mech. 67 (2020), no. 6, 1–53. https://doi.org/10.1145/3424306

[24] P. Toth and D. Vigo, The vehicle routing problem, SIAM, Philadelphia, PA, USA, 2002.

[25] V. Traub and J. Vygen, An improved approximation algorithm for the asymmetric traveling salesman problem, SIAM J. Comput. 51 (2022), no. 1, 139–173. https://doi.org/10.1137/20M1339313

[26] L.A. Wolsey, Heuristic analysis, linear programming and branch and bound, pp. 121–134, Springer Berlin Heidelberg, Berlin, Heidelberg, 1980.