EN|RU

Том 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 г.

 © Институт математики им. С. Л. Соболева, 2015