Approximation of Euclidean k-size cycle cover problem

Abstract

For a fixed natural number k a problem of k collaborating salesmen servicing the same set of cities (nodes of a given graph) is studied. We call this problem the Minimum-weight k-size cycle cover problem (or Min-k-SCCP) due to the fact that it has the following mathematical statement. Let a complete weighted digraph (with loops) be given, it is required to find a minimum-weight cover of the graph by k vertex-disjoint cycles. The problem is a simple generalization of the well-known Traveling Salesman Problem (TSP). We show that Min-k-SCCP is strongly NP-hard in the general case. Metric and Euclidean special cases of the problem are intractable as well. We also prove that Metric Min-k-SCCP belongs to APX class and has 2-approximation polynomial-time algorithm. For Euclidean Min-2-SCCP on the plane, we present a polynomial-time approximation scheme extending the famous result, obtained by S. Arora for Euclidean TSP. Actually, for any fixed c > 1, the scheme finds a (1 + 1/c)-approximate solution of Euclidean Min-2-SCCP in O(n^3(log n)^O(c)) time.