Approximation algorithms for cycle and path partitions in complete graphs (Q7033930)

Given an edge-weighted (metric/general) complete graph with \(n\) vertices, where \(n\bmod k=0\), the maximum weight (metric/general) \(k\)-cycle/path partition problem (\textit{k}CP/\textit{k}PP) asks to find a set of \(\frac nk\) vertex-disjoint \(k\)-cycles/paths such that the total weight is maximized. For \(k=2\), \textit{k}CP and \textit{k}PP are equivalent to the maximum weight perfect matching problem and polynomially solvable. For \(k\ge 3\), metric \textit{k}CP and \textit{k}PP become NP-hard, and general \textit{k}CP and \textit{k}PP become APX-hard even on \(\{0,1\}\)-weighted graphs.\N\NIn this paper, the authors consider approximation algorithms. For metric \(k\)-cycle partition, they improve the previous approximation ratio from \(\frac35\) to \(\frac7{10}\) for \(k=5\), and for \(k>5\) from \(\frac78(1 -\frac1k)^2\) to \((\frac78-\frac1{8k})(1-\frac1k)\) for constant odd \(k>5\) and to \(\frac78(1-\frac1k+\frac1{k(k-1)})\) for even \(k>5\). For metric \(k\)-path partition they improve the approximation ratio from \(\frac78(1-\frac1k)\) to \(\frac{27k^2-48k+16}{32k2-36k-24}\) for \(k\in\{6,8,10\}\). For the case \(k=4\) they improve the approximation ratio from \(\frac34\) to \(\frac56\) for metric 4-cycle partition, from \(\frac23\) to \(\frac34\) for general 4-cycle partition, and from \(\frac34\) to \(\frac{14}{17}\) for metric 4-path partition.