Approximation Algorithms for Packing Cycles and Paths in Complete Graphs

Jingyang Zhao, Mingyu Xiao

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}$ verte…