Skoči na glavni sadržaj

Izvorni znanstveni članak

https://doi.org/10.17535/crorr.2014.0006

Approximation of Euclidean k-size cycle cover problem

Michael Khachay orcid id 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


Puni tekst: engleski pdf 165 Kb

str. 177-188

preuzimanja: 769

citiraj


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

https://hrcak.srce.hr/133695

Datum izdavanja:

30.12.2014.

Posjeta: 1.421 *