Том 21, номер 6, 2014 г., Стр. 11-20
УДК 519.172.2
Глебов А. Н., Замбалаева Д. Ж., Скретнева А. А.
2/3-Приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум
Аннотация:
Получен приближённый алгоритм с оценкой точности 2/3 и кубической оценкой временнóй сложности для несимметричной задачи о двух коммивояжёрах на максимум, состоящей в поиске двух рёберно непересекающихся гамильтоновых циклов с максимальным суммарным весом рёбер в полном ориентированном графе.
Ил. 5, библиогр. 7.
Ключевые слова: задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности, ориентированный граф.
Глебов Алексей Николаевич 1
Замбалаева Долгор Жамьяновна 1
Скретнева Анастасия Андреевна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru, dolgorzam@gmail.com, skretneva@gmail.com
Статья поступила 2 декабря 2013 г.
Исправленный вариант — 11 июля 2014 г.
Литература
[1] Глебов А. Н., Замбалаева Д. Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжерах на максимум // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №4. - С. 17–48.
Glebov A. N., Zambalaeva D. Zh. A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem // J. Appl. Industr. Math. - 2012. - Vol. 6, N1. - P. 69–89.
[2] Kaplan H., Lewenstein M., Shafrir N., SviridenkoM. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs // JACM. - 2005. - Vol. 52, N4. - P. 602–626.
[3] De Kort J. B. J. M. Lower bounds for symmetric K-peripatetic salesman problems // Optimization. - 1991. - Vol. 22, N1. - P. 113–122.
[4] De Kort J. B. J. M. Upper bounds for the symmetric 2-peripatetic salesman problems // Optimization. - 1992. - Vol. 23, N4. - P. 357–367.
[5] De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems // Eur. J. Oper. Res. - 1993. - Vol. 10, N2. - P. 229–243.
[6] Gabow H. N. An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems // Proc. 15th Ann. ACM Symp. Theory of Computing (Boston, April 25–27, 1983). - New York: ACM, 1983. - P. 448–456.
[7] Paluch K., Mucha M., Madry A. A 7/9-approximation algorithm for the maximum traveling salesman problem // APPROX-RANDOM. - 2009. - P. 298–311.
