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 alpha . (k-1/k)(2), where alpha 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.