Let \(G=(V,E)\) be an undirected complete graph on kn vertices. Each edge is associated with a non-negative weight. The edge weights satisfy the triangle inequality. A k-cycle partition is a set of n vertex-disjoint k-cycles, i.e. cycles containing exactly k vertices. The minimum weight k-cycle partition problem (MinWkCP) is to determine a k-cycle partition with minimum total edge weight. In the MinWkCP, if we replace cycles with paths, we obtain the minimum weight k-path partition problem (MinWkPP). In this paper, we first devise a tight \(\frac{3}{2}\) -approximation algorithm for the MinW4CP, improving on the best-known 3-approximation algorithm by Goemans and Williamson (1995). Then we deal with a special case of the MinWkCP and MinWkPP, where the edge weights are either 1 or 2, and propose approximation algorithms with ratios \(\frac{8k^2+14k-8}{7k^2}\) and \(\frac{8(k+1)}{7k}\) , respectively. For the MinW3PP and MinW3CP defined on \(\{1,2\}\) -edge-weighted graphs, we develop two matching based algorithms with tight approximation ratios \(\frac{3}{2}\) and \(\frac{5}{3}\) , respectively. Finally, for the \(\{1,2\}\) -edge-weighted MinW3CP, we design a local search algorithm to further improve the ratio to \(\frac{23}{15}\) .
