Constant-Ratio Polynomial Time Approximation of the Asymmetric Minimum Weight Cycle Cover Problem with Limited Number of Cycles

Articles in Press

Document Type : Original paper

Authors

Mathematical Programming Lab, Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg, Russia

Abstract

We consider polynomial time approximation of the minimum cost cycle cover problem for an edge-weighted digraph, where feasible covers are restricted to have at most $k$ disjoint cycles. In the literature this problem is referred to as Minimum-weight $k$-Size Cycle Cover Problem.  The problem is closely related to the classic Traveling Salesman Problem and Vehicle Routing Problem and has many important applications in algorithms design and operations research. Unlike its unconstrained variant, the studied problem is strongly NP-hard even on undirected graphs and remains intractable in very specific settings. For any metric, the problem can be approximated in polynomial time within ratio 2, while   in fixed-dimensional Euclidean spaces it admits polynomial time approximation schemes. In the same time, approximation of the more general asymmetric variant of the problem still remained weakly studied. In this paper, we propose the first constant-ratio approximation algorithm for this problem, which extends the recent breakthrough results of Svensson-Tarnawski-Végh and Traub-Vygen for the Asymmetric Traveling Salesman Problem.

Keywords

Main Subjects

References

[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´egh, 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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 04 August 2024

Files

Share

How to cite

Statistics