Geodesic
A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 268-278

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: cycle covering of size $k$, traveling salesman problem (tsp), $np$-hard problem, polynomial-time approximation scheme (ptas). 
@article{TIMM_2015_21_3_a26,
     author = {E. D. Neznakhina},
     title = {A {PTAS} for the {Min-}$k${-SCCP} in a {Euclidean} space of arbitrary fixed dimension},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {268--278},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a26/}
}
TY  - JOUR
AU  - E. D. Neznakhina
TI  - A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 268
EP  - 278
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a26/
LA  - ru
ID  - TIMM_2015_21_3_a26
ER  - 
%0 Journal Article
%A E. D. Neznakhina
%T A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 268-278
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a26/
%G ru
%F TIMM_2015_21_3_a26
E. D. Neznakhina. A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 268-278. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a26/