# A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

Preprint · Michel X. Goemans, Yuchong Pan

- Archive id: arxiv:2609.17932
- Published: 2026-09-15
- arXiv: https://arxiv.org/abs/2609.17932
- Source URL: https://arxiv.org/abs/2609.17932
- PDF: https://arxiv.org/pdf/2609.17932
- Provenance: arxiv

## 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 \> 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \\varepsilon)$-approximation algorithm for every $\\varepsilon \> 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.