A PTAS for Min-k-SCCP in Euclidean space of arbitrary fixed dimension

Resumo

We study the minimum weight k-size cycle cover problem (Min-k-SCCP), which consists in partitioning a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem and a special case of the classical vehicle routing problem. It is known that Min-k-SCCP is strongly NP-hard in the general case and preserves its intractability even in the geometric statement. For Euclidean Min-k-SCCP in ℝ^d with k = O(log n), we construct a polynomialtime approximation scheme (PTAS), which generalizes the approach proposed earlier for planar Min-2-SCCP. For each fixed c > 1 the scheme finds a (1 + 1/c)-approximate solution in time \(O\left( {{n^{O\left( d \right)}}{{\left( {\log n} \right)}^{{{\left( {O\left( {\sqrt {dc} } \right)} \right)}^{^{d - 1}}}}}} \right)\).