A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
Michael Khachay, E. D. Neznakhina · Proceedings of the Steklov Institute of Mathematics · 2015
We study the minimum-weight k -size cycle cover problem (Min- k -SCCP) of finding 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 in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora’s approach is built.