Approximability of the minimum-weight k-size cycle cover problem

Michael Khachay () and Katherine Neznakhina
Additional contact information
Michael Khachay: Ural Federal University
Katherine Neznakhina: Ural Federal University

Journal of Global Optimization, 2016, vol. 66, issue 1, No 6, 65-82

Abstract: Abstract The cycle cover problem is a combinatorial optimization problem, which is to find a minimum cost cover of a given weighted digraph by a family of vertex-disjoint cycles. We consider a special case of this problem, where, for a fixed number k, all feasible cycle covers are restricted to be of the size k. We call this case the minimum weight k-size cycle cover problem (Min-k-SCCP). Since each cycle in a cover can be treated as a tour of some vehicle visiting an appropriate set of clients, the problem in question is closely related to the vehicle routing problem. Moreover, the studied problem is a natural generalization of the well-known traveling salesman problem (TSP), since the Min-1-SCCP is equivalent to the TSP. We show that, for any fixed $$k>1$$ k > 1 , the Min-k-SCCP is strongly NP-hard in the general setting. The Metric and Euclidean special cases of the problem are intractable as well. Also, we prove that the Metric Min-k-SCCP belongs to APX class and has a 2-approximation polynomial-time algorithm, even if k is not fixed. 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$$ c > 1 , the scheme finds a $$(1+1/c)$$ ( 1 + 1 / c ) -approximate solution of the Euclidean Min-2-SCCP in $$O(n^3(\log n)^{O(c)})$$ O ( n 3 ( log n ) O ( c ) ) time.

Keywords: Cycle cover problem (CCP); Traveling salesman problem (TSP); NP-hard problem; Polynomial-time approximation scheme (PTAS) (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0391-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:66:y:2016:i:1:d:10.1007_s10898-015-0391-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-015-0391-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().