arXiv preprint ·
Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
An $\mathsf{FPRAS}$ for Mixed Volumes
Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs
Improved lower bounds for the kissing number in dimensions 49 to 61
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.