New Approximation Algorithms for the Minimum Cycle Cover Problem.

Given an undirected weighted graph \(G=(V,E)\) with nonnegative weight function obeying the triangle inequality, a set \(\{C_1,C_2,\ldots ,C_k\}\) of cycles is called a cycle cover if \(V \subseteq \bigcup _{i=1}^k V(C_i)\) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most \(\lambda \) with the minimum number of cycles. An \(O(n^2)\) 24/5-approximation algorithm and an \(O(n^5)\) 14/3-approximation algorithm are given by Yu and Liu (Theor Comput Sci 654:45–58, 2016). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Then we give a new \(O(n^3)\) approximation algorithm that achieves the same ratio 14/3 and has much simpler proof on the approximation ratio. Moreover, we derive an improved 32/7-approximation algorithm that runs in \(O(n^5)\).