{"id":"arxiv/2611.01875","url":"https://arxiv.org/abs/2611.01875","tags":["cs.DS","math.CO"],"score":0,"title":"Approximation Algorithms for Maximum-Weight Degree-Bounded Forests","domain":"cs.DS","source":"arxiv","authors":["Theophile Thiery","Vera Traub","Nicola Widmer"],"reviews":0,"subject":"cs.DS","summary":"In the maximum-weight degree-bounded forest problem, we are given a graph with nonnegative edge weights and a degree upper bound on each vertex. The objective is to find a maximum-weight forest satisfying the degree bounds. We show that this problem admits a simple $2$-approximation via the greedy algorithm. This already improves over the best-known guarantees obtained via a reduction to weighted $3$-matroid parity, and sets a baseline to improve upon. Our main result is an $\\frac{8}{5}$-approximation algorithm for the maximum-weight degree-bounded forest problem. For the special case of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}