Approximation Algorithms for the Maximum-Weight Cycle/Path Packing Problems

Given an undirected complete graph G = (V,E) on kn vertices with a non-negative weight function on E, the maximum-weight k-cycle (k-path) packing problem aims to compute a set of n vertex-disjoint cycles (paths) in G containing k vertices so that the total weight of the edges in these n cycles (paths) is maximized. For the maximum-weight k-cycle packing problem, we develop an algorithm achieving an approximation ratio of α ⋅ (k−1 k )2, where α is the approximation ratio for the maximum traveling salesman problem. For the case k = 4, we design a better 2 3-approximation algorithm. When the weights of edges obey the triangle inequality, we propose a 3 4-approximation algorithm and a 3 5-approximation algorithm for the maximum-weight k-cycle packing problem with k = 4 and k = 5, respectively. For the maximum-weight k-path packing problem with k = 3 (or k = 5) with the triangle inequality, we devise an algorithm with approximation ratio 3 4 and give a tight example.