PTAS для задачи Min-k-SCCP в евклидовом пространстве произвольной фиксированной размерности

Изучается задача Min-$k$-SCCP о разбиении полного взвешенного графа на $k$ вершинно-непересекающихся циклов минимального суммарного веса. Данная задача является обобщением известной задачи коммивояжера (TSP) и частным случаем классической задачи маршрутизации транспорта (VRP). Известно, что задача Min-$k$-SCCP в общем случае $NP$-трудна в сильном смысле и сохраняет свойство труднорешаемости даже в геометрической постановке. Для евклидовой задачи Min-$k$-SCCP в $\mathbb{R}^d$ при $k=O(\log n)$ построена полиномиальная приближенная схема, обобщающая подход, предложенный для решения задачи Min-2-SCCP на плоскости. Для произвольного $c>1$ она находит $(1+1/c)$-приближенное решение задачи за время $O(n^{O(d)} (\log n)^{(O(\sqrt d c))^{d-1}})$.