Том 18, номер 5, 2011 г., Стр. 11-37

УДК 519.8
Глебов A. Н., Замбалаева Д. Ж.
Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями

Аннотация:
Основной результат статьи — приближённый алгоритм с оценкой временнóй сложности O(n⁵) и оценкой точности 4/3 (без учёта аддитивной константы) для задачи о поиске двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном n-вершинном графе с весами рёбер 1 и 2 в случае, когда весовые функции рёбер этих циклов различны (задача о двух коммивояжёрах на минимум с весами рёбер 1 и 2). Этот результат улучшает ранее установленную для задачи оценку точности 11/7.
Ил. 3, библиогр. 10.

Ключевые слова: задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности.

Глебов Алексей Николаевич ^1,2
Замбалаева Долгор Жамьяновна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru, dolgor@ngs.ru

Статья поступила 23 июня 2011 г.

Литература

[1] Агеев А. А., Бабурин А. Е., Гимади Э. Х. Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса // Дискрет. анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 2. — С. 11–20.

[2] Гимади Э. Х., Глазков Ю. В., Глебов А. Н. Приближённые алгоритмы решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2 // Дискрет. анализ и исслед. операций. Сер. 2. — 2007. — Т. 14, № 2. — С. 41–61.

[3] Сердюков А. И. О некоторых экстремальных обходах в графах // Управляемые системы. Сб. науч. тр. — 1978. — Вып. 17. — С. 76–79.

[4] Baburin A. E., Della Croce F., Gimadi E. K., Glazkov Y. V., Paschos V. Th. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 // Discrete Appl. Math. — 2009. — Vol. 157, N 9. — P. 1988–1992.

[5] Berman P., Karpinski M. 8/7-Approximation algorithm for (1,2)-TSP // Proc. of 17th annual ACM–SIAM symposium on discrete algorithms, SODA 2006 (Miami, January 22—26, 2006). — New York: ACM Press, 2006. — P. 641–648.

[6] Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // Technical report CS-93-19: Carnegie Mellon University, 1976.

[7] De Kort J. B. J. M. Lower bounds for symmetric $K$-peripatetic salesman problems // Optimization. — 1991. — Vol. 22, N 1. — P. 113–122.

[8] De Kort J. B. J. M. Upper bounds for the symmetric 2-peripatetic salesman problem // Optimization. — 1992. — Vol. 23, N 4. — P. 357–367.

[9] De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems // Eur. J. Oper. Res. — 1993. — Vol. 70, N 2. — P. 229–243.

[10] Papadimitriou C. H., Yannakakis M. The traveling salesman problem with distances one and two // Math. Oper. Res. — 1993. — Vol. 18. N 1. — P. 1–11.