Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 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.