{"ID":22918833,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17932","arxiv_id":"2609.17932","title":"A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution","abstract":"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, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \\sqrt{2} + \\varepsilon) \\approx (2.914 + \\varepsilon)$-approximation algorithm for the demand matching problem for every $\\varepsilon \u003e 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \\varepsilon)$-approximation algorithm for every $\\varepsilon \u003e 0$. Both algorithms run in time polynomial in $1/\\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \\in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2609.17932","url_pdf":"https://arxiv.org/pdf/2609.17932v1","authors":"[\"Michel X. Goemans\",\"Yuchong Pan\"]","published":"2026-09-15T23:44:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}