Полиномиальная приближенная схема для евклидовой задачи о цикловом покрытии графа

Изучается задача Min-$k$-SCCP о разбиении полного взвешенного орграфа на $k$ вершинно-непересекающихся циклов минимального суммарного веса, являющаяся естественным обобщением известной задачи коммивояжера (TSP) и обладающая рядом практических приложений в исследовании операций и анализе данных. Показано, что задача в общем случае $NP$-трудна в сильном смысле и сохраняет свойство труднорешаемости даже в геометрической постановке. Для метрического случая предложен $2$-приближенный алгоритм. Для евклидовой задачи Min-$2$-SCCP построена полиномиальная приближенная схема, основанная на подходе С. Ароры.