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 + √2 + ε) ≈ (2.914 + ε)-approximation algorithm for the demand matching problem for every ε > 0, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized (2 + ε)-approximation algorithm for every ε > 0. Both algorithms run in time polynomial in 1/ε 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 ∈ [0, 1], which may be of independent interest. The balance guarantee 1/(1+q) is tight in the worst case over all knapsack instances.
Related
- Matroid Contention Resolution with Concentration
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
- An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
- A geometrically linear approximation of min-max optimal matching
- An energy-decreasing algorithm for the finite element approximation of ferronematic equilibrium states and its numerical realization
BibTeX
@misc{goemans2026betterthan3,
title = {{A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution}},
author = {Michel X. Goemans and Yuchong Pan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17932},
eprint = {2609.17932},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17932},
}
RIS
TY - UNPB
TI - A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
AU - Michel X. Goemans
AU - Yuchong Pan
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17932
UR - https://arxiv.org/abs/2609.17932
AB - 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 + √2 + ε) ≈ (2.914 + ε)-approximation algorithm for the demand matching problem for every ε > 0, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized (2 + ε)-approximation algorithm for every ε > 0. Both algorithms run in time polynomial in 1/ε 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 ∈ [0, 1], which may be of independent interest. The balance guarantee 1/(1+q) is tight in the worst case over all knapsack instances.
ER -