Том 18, номер 4, 2011 г., Стр. 17-48

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

Аннотация:
Рассматривается задача об отыскании в полном неориентированном графе двух рёберно-непересекающихся гамильтоновых циклов с максимальным суммарным весом рёбер. Для этой задачи получен алгоритм с гарантированной оценкой точности 7/9, наилучшей на сегодняшний день, и кубической временнóй сложностью. В случае, когда веса рёбер графа принимают значения из заданного промежутка [1, q], разработана модификация алгоритма, имеющая оценку точности (7q + 3)/(9q + 1), также наилучшую на сегодняшний день, и кубическую временнýю сложность.
Ил. 5, библиогр. 15.

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

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

Статья поступила 25 января 2011 г.
Исправленный вариант — 6 мая 2011 г.

Литература

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

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

[3] Сердюков А. И. Алгоритм с оценкой для задачи коммивояжёра на максимум // Управляемые системы. Сб. науч. тр. Вып. 25. — Новосибирск: Ин-т математики СО АН СССР, 1984. - С. 80-86.

[4] Chen Z.-Z., Okamoto Y., Wang L. Improved deterministic approximation algorithms for Max TSP // Inf. Process. Lett. — 2005. — Vol. 95, N 2. - P. 333-342.

[5] Chen Z.-Z., Wang L. An improved randomized approximation algorithm for Max TSP // J. Comb. Optim. - 2005. - Vol. 9, N 4. - P. 401-432.

[6] DeBrey M. J. D., Voigenant A. Well-solved cases of the 2-peripatetic salesman problem // Optimization. — 1997. — Vol. 39, N 3. - P. 275-293.

[7] DeKort 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 // Europ. J. Oper. Res. — 1993. — Vol. 70, N2. - P. 229-243.

[10] Duchenne E., Laporte G., Semet F. Branch-and-cut algorithms for the undirected $m$-peripatetic salesman problem // Europ. J. Oper. Res. — 2005. — Vol. 162, N 3. - P. 700-712.

[11] Gabow H. N. An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems // Proc. 15th Annu. ACM Symp. Theory of Comput. (Boston, April 25-27, 1983). — New York: ACM, 1983. — P. 448-456.

[12] Hassin R., Rubinstein S. Better approximations for max TSP // Inf. Process. Lett. - 2000. - Vol. 75, N 4.-P. 181-186.

[13] Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974) — NATO Advanced Study Inst. Ser., Ser. C: Math, and Phys. Sci., Vol. 19. — Dordrecht: Reidel, 1975. — P. 173-178.

[14] van Zuylen A. Multiplying pessimistic estimators: deterministic approximation of max TSP and maximum triangle packing // Computing and Combinatorics, 16th Annu. Int. Conf. COCOON 2010 (Nha Trang, Vietnam, July 19-21, 2010). Proc. Vol. 6196.)