A Polynomial-Time Approximation Scheme for the Euclidean Problem on a Cycle Cover of a Graph / Khachai M. Yu.,Neznakhina E. D. // PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS. - 2015. - V. 289, l. 1. - P. S111-S125.

ISSN/EISSN:

0081-5438 / 1531-8605

Type:

Article

Abstract:

We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly NP-hard in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora's approach is built.

Author keywords:

NP-hard problem; polynomial-time approximation scheme; traveling salesman problem; cycle cover of size k ALGORITHMS; SALESMAN

DOI:

10.1134/S0081543815050107

Web of Science ID:

ISI:000356931500010

Соавторы в МНС:

Другие поля

Поле	Значение
Month	JUL
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1531-8605
Keywords-Plus	ALGORITHMS; SALESMAN
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	mkhachay@imm.uran.ru eneznakhina@yandex.ru
ResearcherID-Numbers	Khachay, Michael/H-3251-2013
ORCID-Numbers	Khachay, Michael/0000-0003-3555-0080
Funding-Acknowledgement	Russian Science Foundation {[}14-11-00109]
Funding-Text	This work was supported by the Russian Science Foundation (project no. 14-11-00109).
Number-of-Cited-References	17
Usage-Count-Last-180-days	2
Usage-Count-Since-2013	5
Journal-ISO	Proc. Steklov Inst. Math.
Doc-Delivery-Number	CL4OD