Polynomial-time approximation scheme for a~Euclidean problem on a~cycle covering of a~graph
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 4, pp. 297-311
Voir la notice de l'article provenant de la source Math-Net.Ru
We study the Min-$k$-SCCP problem on a partition of a complete weighted digraph into $k$ vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known Traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly $NP$-hard and preserves intractability even in the geometric statement. For a metric special case of the problem, a new polynomial $2$-approximation algorithm is proposed. For the Euclidean Min-$2$-SCCP, a polynomial-time approximation scheme based on Arora's approach is built.
Keywords:
$NP$-hard problem, polynomial-time approximation scheme (PTAS), traveling salesman problem (TSP), cycle covering of size $k$.
@article{TIMM_2014_20_4_a25,
author = {M. Yu. Khachai and E. D. Neznakhina},
title = {Polynomial-time approximation scheme for {a~Euclidean} problem on a~cycle covering of a~graph},
journal = {Trudy Instituta matematiki i mehaniki},
pages = {297--311},
publisher = {mathdoc},
volume = {20},
number = {4},
year = {2014},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/TIMM_2014_20_4_a25/}
}
TY - JOUR AU - M. Yu. Khachai AU - E. D. Neznakhina TI - Polynomial-time approximation scheme for a~Euclidean problem on a~cycle covering of a~graph JO - Trudy Instituta matematiki i mehaniki PY - 2014 SP - 297 EP - 311 VL - 20 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/TIMM_2014_20_4_a25/ LA - ru ID - TIMM_2014_20_4_a25 ER -
%0 Journal Article %A M. Yu. Khachai %A E. D. Neznakhina %T Polynomial-time approximation scheme for a~Euclidean problem on a~cycle covering of a~graph %J Trudy Instituta matematiki i mehaniki %D 2014 %P 297-311 %V 20 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/item/TIMM_2014_20_4_a25/ %G ru %F TIMM_2014_20_4_a25
M. Yu. Khachai; E. D. Neznakhina. Polynomial-time approximation scheme for a~Euclidean problem on a~cycle covering of a~graph. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 4, pp. 297-311. http://geodesic.mathdoc.fr/item/TIMM_2014_20_4_a25/