Том 16, номер 4, 2009 г., Стр. 3-20

УДК 519.178
А. А. Агеев, А. В. Пяткин
Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2

Аннотация:
В задаче $m$-PSP требуется в заданном $n$-вершинном полном неориентированном взвешенном графе найти $m$ непересекающихся гамильтоновых циклов наименьшего суммарного веса. Эта задача была впервые рассмотрена Крарупом в 1974 г.; она имеет применения в задачах дизайна сетей и теории расписаний. Известно, что задача 2-PSP NP-трудна даже в метрическом случае, а в общем случае для неё не существует приближённого алгоритма с точностью, ограниченной константным множителем. Бабурин, Гимади и Коркишко (2004) предложили приближённый алгоритм с точностью $(9/4+\varepsilon)$ для метрической задачи 2-PSP, основанный на решении задачи коммивояжёра. В настоящей статье представлен улучшенный приближённый алгоритм с точностью 2 и временем работы $O(n^2\log n)$ для метрической задачи 2-PSP. Этот алгоритм использует тот факт, что задача поиска двух непересекающихся остовных деревьев минимального суммарного веса является полиномиально разрешимой.
Ил. 5, библиогр. 12.

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

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

Статья поступила 21 февраля 2009 г.
Исправленный вариант — 12 мая 2009 г.