hrcak mascot   Srce   HID

Croatian Operational Research Review, Vol. 5 No. 2, 2014.

Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2014.0006

Approximation of Euclidean k-size cycle cover problem

Michael Khachay   ORCID icon 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: 285* citiraj
APA 6th Edition
Khachay, M. i Neznakhina, K. (2014). Approximation of Euclidean k-size cycle cover problem. Croatian Operational Research Review, 5 (2), 177-188. https://doi.org/10.17535/crorr.2014.0006
MLA 8th Edition
Khachay, Michael i Katherine Neznakhina. "Approximation of Euclidean k-size cycle cover problem." Croatian Operational Research Review, vol. 5, br. 2, 2014, str. 177-188. https://doi.org/10.17535/crorr.2014.0006. Citirano 18.02.2019.
Chicago 17th Edition
Khachay, Michael i Katherine Neznakhina. "Approximation of Euclidean k-size cycle cover problem." Croatian Operational Research Review 5, br. 2 (2014): 177-188. https://doi.org/10.17535/crorr.2014.0006
Harvard
Khachay, M., i Neznakhina, K. (2014). 'Approximation of Euclidean k-size cycle cover problem', Croatian Operational Research Review, 5(2), str. 177-188. doi: https://doi.org/10.17535/crorr.2014.0006
Vancouver
Khachay M, Neznakhina K. Approximation of Euclidean k-size cycle cover problem. Croatian Operational Research Review [Internet]. 2014 [pristupljeno 18.02.2019.];5(2):177-188. doi: https://doi.org/10.17535/crorr.2014.0006
IEEE
M. Khachay i K. Neznakhina, "Approximation of Euclidean k-size cycle cover problem", Croatian Operational Research Review, vol.5, br. 2, str. 177-188, 2014. [Online]. doi: https://doi.org/10.17535/crorr.2014.0006

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 fi xed 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

Posjeta: 428 *