Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса

Рассматривается задача нахождения двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном взвешенном графе, в котором для весов выполняется неравенство треугольника. Показано, что задача NP-трудна в сильном смысле. Предложены два приближенных алгоритма с временной сложностью $O(n^3)$ в случае, когда на ребрах графа задана одна весовая функция и когда заданы две весовые функции. Показано, что соответствующие оценки точности асимптотически (с ростом $n$) равны 9/4 и 12/5.