{"id":"arxiv/2609.17932","url":"https://arxiv.org/abs/2609.17932","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution","domain":"cs.DS","source":"arxiv","authors":["Michel X. Goemans","Yuchong Pan"],"reviews":0,"subject":"cs.DS","summary":"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, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}