Том 19, номер 1, 2012 г., Стр. 17-32
УДК 519.8
Гимади А. Ю., Ивонина Е. В.
Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум
Аннотация:
Рассматривается задача отыскания в полном неориентированном графе двух рёберно непересекающихся гамильтоновых циклов (маршрутов коммивояжёра) с максимальным суммарным весом. Для случая весов рёбер из отрезка$[1,q]$ представлен полиномиальный алгоритм с гарантированной оценкой точности$\frac{3q+2}{4q+1}$ . В случае весов 1 и 2 и двух различных весовых функций, соответствующих двум маршрутам, предложен полиномиальный алгоритм с оценкой точности$\frac{11\rho-8}{18\rho-15}$ , где$\rho$ – оценка точности некоторого алгоритма решения аналогичной задачи на минимум.
Ил. 1, библиогр. 13.
Ключевые слова: задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности.
Гимади Эдуард Хайрудтинович 1,2
Ивонина Евгения Викторовна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, evivonina@gmail.com
Статья поступила 31 мая 2011 г.
Исправленный вариант — 1 июля 2011 г.
Литература
[1] Агеев А. А., Бабурин А. Е., Гимади Э. Х. Полиномиальный алгоритм с оценкой 3/4 для нахождения двух рёберно непересекающихся гамильтоновых циклов максимального суммарного веса // Дискрет. анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 2. — С. 11–20.
[2] Гимади Э. Х., Глазков Ю. В., Глебов А. Н. Приближённые алгоритмы решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2 // Дискрет. анализ и исслед. операций. Сер. 2. — 2007. — Т. 14, № 2. — C. 41–61.
[3] Глебов А. Н., Замбалаева Д.Ж. Задача о двух коммивояжёрах на минимум в полном графе с различными весовыми функциями // Дискрет. анализ и исслед. операций. — 2011. — Т. 16, № 4. — C. 17–48.
[4] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.
[5] Сердюков А. И. Алгоритм с оценкой для задачи коммивояжёра на максимум // Управляемые системы. — 1984. — Вып. 25. — С. 80–86.
[6] Baburin A. E., Croce F. D., Gimadi E. Kh., Glazkov Y. V., Paschos V. Th. Approximation algorithms for the 2-peripatetic sales?man problem with edge weights 1 and 2 // Discrete Appl. Math. — 2009. — Vol. 157, N 9. — P. 1988–1992.
[7] De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems // Eur. J. Oper. Res. — 1993. — Vol. 10, N 2. — P. 229–243.
[8] Gabow H. N. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems // Proc. 15th Ann. ACM Symp. Theory of Computing (Boston, April 25–27, 1983). — New York: ACM Press, 1983. — P. 448–456.
[9] Glebov A. N., Gordeeva A. V., Zambalaeva D. Zh. 7/5-Approximation algorithm for a 2-peripatetic salesman problem on minimum with different weight functions valued 1 and 2 // Discrete Appl. Math. — 2010, submitted.
[10] Gutin G., Punnen A. P. The traveling salesman problem and its variations // Boston; London; Dordrecht: Kluwer Acad. Publ., 2002. — 830 p.
[11] Krarup J. The peripatetic salesman and some related unsolved problems // Combinatorial programming: methods and applications (Proc. NATO Ad-vanced Study Inst., Versailles, 1974). — Reidel; Dordrecht: Kluwer Acad. Publ., 1975. — P. 173–178.
[12] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. The traveling salesman problem: a guided tour of combinatorial optimization. — Chichester: Wiley, 1985. — 463 p.
[13] 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.
