Approximate Generalized Matching: $f$-Factors and $f$-Edge Covers

Dawei Huang, Seth Pettie

In this paper we present linear time approximation schemes for several generalized matching problems on nonbipartite graphs. Our results include $O_{\epsilon }(m)$-time algorithms for $(1-ε)…