EN|RU

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

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

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

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

Глебов Алексей Николаевич 1,2
Замбалаева Долгор Жамьяновна 1

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

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

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