Approximation Algorithms for Packing Cycles and Paths in Complete Graphs

Given an edge-weighted (metric/general) complete graph with $n$ vertices, the maximum weight (metric/general) $k$-cycle/path packing problem is to find a set of $\frac{n}{k}$ vertex-disjoint $k$-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric $k$-cycle packing, we improve the previous approximation ratio from $3\mathrm{/}5$ to $7\mathrm{/}10$ for $k=5$, and from $7\mathrm{/}8\cdot (1-1\mathrm{/}k{)}^2$ for $k>5$ to $(7\mathrm{/}8-0.125\mathrm{/}k)(1-1\mathrm{/}k)$ for constant odd $k>5$ and to $7\mathrm{/}8\cdot (1-1\mathrm{/}k+\frac{1}{k(k-1)})$ for even $k>5$. For metric $k$-path packing, we improve the approximation ratio from $7\mathrm{/}8\cdot (1-1\mathrm{/}k)$ to $\frac{27k^2-48k+16}{32k^2-36k-24}$ for even $10\ge k\ge 6$. For the case of $k=4$, we improve the approximation ratio from $3\mathrm{/}4$ to $5\mathrm{/}6$ for metric 4-cycle packing, from $2\mathrm{/}3$ to $3\mathrm{/}4$ for general 4-cycle packing, and from $3\mathrm{/}4$ to $14\mathrm{/}17$ for metric 4-path packing.