УДК 519.16 + 519.85
MSC: 68W25
DOI: 10.21538/0134-4889-2023-29-3-261-273
Исследования поддержаны Российским научным фондом, грант № 22-21-00672, https://rscf.ru/ project/22-21-00672/
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2023, Vol. 323, Suppl. 1, pp. S121–S132. (Abstract)
В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (ATSP) в классе алгоритмов с фиксированными гарантиями точности. Как и знаменитый алгоритм Кристофидеса — Сердюкова для симметричных маршрутных задач, данные прорывные результаты, применяемые в качестве "черного ящика", позволили разработать первые полиномиальные приближенные алгоритмы с константными факторами аппроксимации для серии близких комбинаторных задач. Одновременно выявились задачи, в которых этот простой подход, основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху. В данной статье подход Свенссона — Трауб распространяется на более широкий класс задач о покрытии минимального веса взвешенного ориентированного графа ограниченным сверху числом циклов. В частности, впервые показывается, что задача о покрытии графа не более чем $k$ циклами допускает полиномиальную аппроксимацию с константной точностью $\max\{22+\varepsilon, 4 + k\}$ для произвольного $\varepsilon>0$.
Ключевые слова: цикловое покрытие графа, асимметричная задача коммивояжера, приближенный алгоритм с константным фактором аппроксимации
СПИСОК ЛИТЕРАТУРЫ
1. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016. 220 c.
2. Sahni S., Gonzales T. P-complete approximation problems // Journal of the ACM. 1976. Vol. 23. P. 555–565.
3. Bläser Markus, Siebert Bodo. Computing cycle covers without short cycles // Algorithms — ESA 2001 ed. F. Meyer auf der Heide. Berlin; Heidelberg: Springer-Verlag, 2001. P. 368–379. (Lecture Notes in Computer Science; vol. 2161). 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. P. 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. P. 181–206. doi: 10.1137/060676003
6. Manthey Bodo. Minimum-weight cycle covers and their approximability // Discrete Appl. Math. 2009. Vol. 157, no. 7. P. 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. P. 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. P. 65–82.
9. Е. Д. Незнахина. PTAS для задачи Min-k-SCCP в евклидовом пространстве произвольной фиксированной размерности // Тр. Ин-та математики и механики УрО РАН. 2015. Vol. 21, no. 3. P. 268–278.
10. Э. Х. Гимади, И. А. Рыков Асимптотически точный подход к приближенному решению некоторых задач покрытия графа // Тр. Ин-та математики и механики УрО РАН. 2015. Vol. 21, no. 3. P. 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. 2016. Vol. 93. P. 117–120. doi: 10.1134/S1064562416010233
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. NY; San Francisco; London: Acad. Press., 1976. P. 441.
13. Сердюков А.И. О некоторых экстремальных обходах в графах // Управляемые системы. 1978. №. 17. P. 76–79.
14. Wolsey Laurence A. Heuristic analysis, linear programming and branch and bound // 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. P. 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. P. 139–173. doi: 10.1137/20M1339313
18. М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко. Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера // Тр. Ин-та математики и механики УрО РАН. 2022. Vol. 29, no. 3. P. 241–258. doi: 10.21538/0134-4889-2022-28-3-241-258
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. P. 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. P. 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. P. 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. P. 23–39. doi: 10.1002/net.3230120103
23. Schrijver A. Combinatorial optimization — polyhedra and efficiency. NY: Springer, 2003, 1189 p.
Поступила 4.08.2023
После доработки 18.08.2023
Принята к публикации 21.08.2023
Хачай Михаил Юрьевич
чл.-корр. РАН
д-р физ.-мат. наук
зав. отделом
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: mkhachay@imm.uran.ru
Незнахина Екатерина Дмитриевна
канд. физ.-мат. наук
старший науч. сотрудник
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет им. Б.Н. Ельцина
г. Екатеринбург
e-mail: eneznakhina@yandex.ru
Рыженко Ксения Валерьевна
аспирант, математик
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: kseniarizhenko@gmail.com
Ссылка на статью: М.Ю. Хачай, Е.Д. Незнахина, К.В. Рыженко. Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 261-273
English
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
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
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.
[References -> on the "English" button bottom right]
