آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,878 |
| تعداد دریافت فایل اصل مقاله | 1,060,651 |
Constant-Ratio Polynomial Time Approximation of the Asymmetric Minimum Weight Cycle Cover Problem with Limited Number of Cycles | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 14 مرداد 1403 اصل مقاله (440.43 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29138.1860 | ||
| نویسندگان | ||
| Michael Yu. Khachay* ؛ Katherine Neznakhina؛ Ksenia Rizhenko | ||
| Mathematical Programming Lab, Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg, Russia | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Approximation algorithm؛ constant approximation ratio؛ Asymmetric Traveling Salesman Problem؛ Cycle Cover Problem | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 69 تعداد دریافت فایل اصل مقاله: 268 |
||