Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach

Eric Angel, Nguyen Kim Thang, Shikha Singh

In this paper, we study the $k$-forest problem in the model of resource augmentation. In the $k$-forest problem, given an edge-weighted graph $G(V,E)$, a parameter $k$, and a set o…