М.Ю. Хачай, Е.Д. Незнахина, К.В. Рыженко. Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов ... С. 261-273

УДК 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/ 

В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (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 .

[References -> on the "English" button bottom right]