2026/08/04 by Yuchong Pan, Michel X. Goemans
Computer Science · Mathematics · #cs.DS #cs.DM #math.CO
arxiv created 2026/08/04 · arxiv updated 2026/08/06
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 (α, β)-bicriteria approximation algorithms, which return a solution of weight at least 1/α times the optimum while allowing an additive capacity violation of at most β 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 β= 0 and all β≥ 1, completely characterizing the trade-off between weight approximation and additive capacity violation in this range.