Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум

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