УДК 519.176
MSC: 05C38, 05C70, 05C85, 68R05, 90B06, 90B10, 90C27
DOI: 10.21538/0134-4889-2018-24-3-272-280
Полный текст статьи
Исследование выполнено при финансовой поддержке РНФ (проект 16-11-10041).
Цикловым покрытием графа называется остовный подграф, компоненты связности которого являются простыми циклами. Рассматривается труднорешаемая задача отыскания в полном взвешенном ориентированном графе циклового покрытия максимального веса, которое удовлетворяет верхнему ограничению на количество входящих в него циклов и нижнему ограничению на количество дуг в каждом цикле. Предложен полиномиальный алгоритм решения этой задачи в геометрическом случае, когда вершины заданного графа являются точками в многомерном вещественном пространстве, а расстояния между ними индуцированы положительно однородной функцией, единичный шар которой является произвольным выпуклым политопом с фиксированным числом фасет. Полученный результат развивает идеи, лежащие в основе известного алгоритма для полиэдральной задачи коммивояжера на максимум.
Ключевые слова: цикловое покрытие, задача коммивояжера, полиэдральная метрика, оптимальное решение, полиномиальный алгоритм
СПИСОК ЛИТЕРАТУРЫ
1. Сердюков А.И. Асимптотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Методы целочисленной оптимизации. Управляемые системы, вып. 27. Новосибирск: Ин-т математики СО АН СССР, 1987. С. 79–87.
2. Сердюков А.И. Задача коммивояжера на максимум в конечномерных вещественных пространствах // Дискретный анализ и исследование операций. 1995. Т. 2, № 1. С. 50–56.
3. Шенмайер В.В. Асимптотически точный алгоритм для задачи коммивояжера на максимум в конечномерном нормированном пространстве // Дискретный анализ и исследование операций. 2010. Т. 17, № 4. С. 84–91.
4. Barvinok A., Fekete S. P., Johnson D. S., Tamir A., Woeginger G. J., Woodroofe R. The geometric maximum traveling salesman problem // J. ACM. 2003. Vol. 50, no. 5. P. 641–664. doi: 10.1145/876638.876640 .
5. Bl$\ddot{\mathrm{a}}$ser M., Manthey B. Approximating maximum weight cycle covers in directed graphs with weights zero and one // Algorithmica. 2005. Vol. 42, no. 2. P. 121–139. doi: 10.1007/s00453-004-1131-0 .
6. Cayley A. A theorem on trees // Quart. J. Pure Appl. Math. 1889. Vol. 23. P. 376–378.
7. Engebretsen L., Karpinski M. TSP with bounded metrics // J. Comp. System Sci. 2006. Vol. 72, no. 4. P. 509–546. doi: 10.1016/j.jcss.2005.12.001 .
8. Kaplan H., Lewenstein M., Shafrir N., Sviridenko M. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs // J. ACM. 2005. Vol. 52, no. 4. P. 602–626. doi: 10.1145/1082036.1082041 .
9. Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. The traveling salesman problem: a guided tour of combinatorial optimization. N Y: Wiley, 1985. 465 p. ISBN: 0-471-90413-9 .
10. Manthey B. On approximating restricted cycle covers // Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA 2005). Berlin: Springer, 2006. P. 282–295. (Lecture Notes in Computer Science; vol. 3879.) doi: 10.1007/11671411_22 .
11. Paluch K., Mucha M., Madry A. A 7/9-approximation algorithm for the maximum traveling salesman problem // Proc. 12th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2009). Berlin: Springer, 2009. P. 298–311. (Lecture Notes in Computer Science; vol. 5687.) doi: 10.1007/978-3-642-03685-9_23 .
12. Shenmaier V. V. Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP // Discrete Appl. Math. 2014. Vol. 163, part 2. P. 214–219. doi: 10.1016/j.dam.2012.09.007 .
13. Shenmaier V. V. Complexity and approximation of the smallest k-enclosing ball problem // European J. Combinatorics. 2015. Vol. 48, no. C. P. 81–87. doi: 10.1016/j.ejc.2015.02.011 .
14. Zemel E. An O(n) algorithm for the linear multiple choice knapsack problem and related problems // Inf. Proc. Lett. 1984. Vol. 18, no. 3. P. 123–128. doi: 10.1016/0020-0190(84)90014-0 .
Поступила 23.04.2018
Шенмайер Владимир Владимирович
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики им. С.Л.Соболева СО РАН,
г. Новосибирск
e-mail: shenmaier@mail.ru
English
V.V. Shenmaier. An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles
A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case when the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.
Keywords: cycle cover, Max TSP, polyhedral metric, optimal solution, polynomial-time algorithm
The paper was received by the Editorial Office on May 8, 2018.
Funding Agency: This work was supported by the Russian Science Foundation (project no. 16-11-10041).
Vladimir Vladimirovich Shenmaier, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics SB RAS, Novosibirsk, 630090 Russia, e-mail: shenmaier@mail.ru
[References -> on the "English" button bottom right]
