Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2014.0006
Approximation of Euclidean k-size cycle cover problem
Michael Khachay
orcid.org/0000-0003-3555-0080
; Krasovsky Institute of Mathematics and Mechanics, Ural Federal University
Katherine Neznakhina
; Krasovsky Institute of Mathematics and Mechanics, Ural Federal University
Sažetak
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 Minimumweight k-size cycle cover problem (or Min-k-SCCP) due to the fact that the problem 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 the Metric Min-k-SCCP belongs to the APX class and has a 2-approximation polynomial-time algorithm. For the Euclidean Min-2-SCCP in the plane, we present a polynomial-time approximation scheme extending the famous result obtained by S. Arora for the Euclidean TSP. Actually, for any fixed c > 1, the scheme finds a (1 + 1/c)-approximate solution of the Euclidean Min-2-SCCP in O(n^3(log n)^O(c)) time.
Ključne riječi
vertex-disjoint cycle cover; Traveling Salesman Problem (TSP); NP-hard problem; polynomial-time approximation scheme (PTAS)
Hrčak ID:
133695
URI
Datum izdavanja:
30.12.2014.
Posjeta: 1.832 *