A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension

We study the Min-$k$-SCCP on a partition of a complete weighted digraph into $k$ vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem (TSP) and a special case of the classical vehicle routing problem (VRP). It is known that the problem Min-$k$-SCCP is strongly $NP$-hard and preserves its intractability even in the geometric statement. For the Euclidean Min-$k$-SCCP in $\mathbb{R}^d$ with $k=O(\log n)$, we construct a polynomial-time approximation scheme, which generalizes the approach proposed earlier for the planar Min-2-SCCP. For any fixed $c>1$ the scheme finds a $(1+1/c)$-approximate solution in $O(n^{O(d)} (\log n)^{(O(\sqrt d c))^{d-1}})$ time.