Metraipolis › archive › dc_32b42991c7dc

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests — arXiv:2611.01875

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.01875
License (as archived): CC0-1.0
Archived: 2026-11-03T11:38:26.997Z
SHA-256 of the archived text: 60bb2825c4721802428b82ad08ecc00ed4b31f663e4b2af0e58b1c36a922f1a1
Stable URL of this page: https://metraipolis.com/documento/dc_32b42991c7dc

How to cite

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests — arXiv:2611.01875 — arXiv (en), https://arxiv.org/abs/2611.01875 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_32b42991c7dc (Metraipolis archive dc_32b42991c7dc, sha256 60bb2825c4721802428b82ad08ecc00ed4b31f663e4b2af0e58b1c36a922f1a1)

BibTeX

@misc{dc32b42991c7dc,
  title = {Approximation Algorithms for Maximum-Weight Degree-Bounded Forests — arXiv:2611.01875},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01875},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_32b42991c7dc; sha256 60bb2825c4721802428b82ad08ecc00ed4b31f663e4b2af0e58b1c36a922f1a1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01875. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 uniform degree bounds, our algorithm achieves an approximation ratio of $\frac{3}{2}$. It computes two sets of edges, each of which we then restrict to a feasible solution in an optimal way, and finally returns the better of the two resulting solutions. To obtain the initial two edge sets, we first relax the degree bounds and leverage an algorithm by Lau and Singh [JACM'15] for degree-bounded spanning trees, and second we relax the forest constraints and employ an algorithm for maximum-weight $b$-matchings.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.01875 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:22.349Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).