Delphi.science

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests

Theophile Thiery, Vera Traub, Nicola Widmer

arXivarxiv/2611.01875Nov 1, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.01875
curl -X POST /api/v1/records/arxiv/2611.01875/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01875/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'