Metraipolis › archive › dc_601d26cc8cda

Bicriteria Approximation Algorithms for Demand Matching — arXiv:2608.04223

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.04223
License (as archived)
CC0-1.0
Archived
2026-10-31T11:46:07.212Z
SHA-256 of the archived text
5799c741a4656799f99bb9eba191ece02abdb672c192959a3480061a75d4ad3e
Stable URL of this page
https://metraipolis.com/documento/dc_601d26cc8cda

How to cite

Bicriteria Approximation Algorithms for Demand Matching — arXiv:2608.04223 — arXiv (en), https://arxiv.org/abs/2608.04223 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_601d26cc8cda (Metraipolis archive dc_601d26cc8cda, sha256 5799c741a4656799f99bb9eba191ece02abdb672c192959a3480061a75d4ad3e)
BibTeX
@misc{dc601d26cc8cda,
  title = {Bicriteria Approximation Algorithms for Demand Matching — arXiv:2608.04223},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04223},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_601d26cc8cda; sha256 5799c741a4656799f99bb9eba191ece02abdb672c192959a3480061a75d4ad3e},
  year = {2026}
}

Archived text

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

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a capacity, and the goal is to find a maximum weight subset of edges whose total incident demand at every vertex does not exceed its capacity. We study $(\alpha, \beta)$-bicriteria approximation algorithms, which return a solution of weight at least $1/\alpha$ times the optimum while allowing an additive capacity violation of at most $\beta$ times the maximum edge demand. We give an iterative relaxation algorithm for the demand matching problem that exploits a structural characterization of strictly fractional extreme points of the natural LP relaxation, which reduces the residual rounding problem to odd-cycle instances. Combined with a better-of-two rounding strategy, this yields $(7/6, 1)$- and $(1, 1)$-bicriteria approximation algorithms for general and bipartite graphs, respectively. We further generalize this approach to obtain a parametric family of algorithms, including a $(1, 4/3)$-bicriteria approximation. Separately, for the more general $k$-hypergraph demand matching problem, we give a greedy, combinatorial $(k, 1)$-bicriteria approximation algorithm. We complement these algorithmic results with matching lower bounds relative to the natural LP relaxation for $\beta = 0$ and all $\beta \geq 1$, completely characterizing the trade-off between weight approximation and additive capacity violation in this range.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in math.CO).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.04223 — 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-10-31T11:35:10.113Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).