Асимптотически точный подход к приближенному решению некоторых задач покрытия графа несмежными циклами

Рассматривается задача $m$-CYCLES COVER о покрытии полного неориентированного графа $m$ вершинно-несмежными циклами экстремального суммарного веса ребер. Представлен общий так называемый TSP-подход к построению приближенного алгоритма решения задачи с использованием решения задачи коммивояжера (TSP). Проведен анализ модификаций алгоритма для задачи Euclidean MAX $m$-CYCLES COVER на детерминированных входах (весах ребер) в многомерном евклидовом пространстве и для задачи Random MIN $m$-CYCLES COVER на случайных входах UNI$(0,1)$. Показано, что оба алгоритма имеют временную сложность $O(n^3)$ и являются асимптотически точными при числе покрывающих циклов $m=o(n)$ и $ m\le n^{1/3}/\ln n$ соответственно.