Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension

摘要

We study the Min- k -SCCP on the partition of a complete weighted digraph by k vertex-disjoint cycles of minimum total weight. This problem is the generalization of the well-known traveling salesman problem (TSP) and the special case of the classical vehicle routing problem (VRP). It is known that the problem Min- k -SCCP is strongly NP-hard and remains intractable even in the geometric statement. For the Euclidean Min- k -SCCP in R d , 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 time of O(n d+1 (k log n ) ( O (√dc))d-1 2 k ).