Improved algorithm finds better matches under capacity limits
A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The demand matching problem is about picking edges in a network without exceeding the capacity limits of each connection point. Previous methods could only guarantee solutions about three times worse than the best possible. The authors developed a new approach that improves this guarantee to slightly less than three, and even better for some special cases. They achieved this by using a stronger mathematical model and a novel technique called contention resolution. This means we can now find better solutions faster in problems involving limited resources on networks.
What this means in practice
- •For network schedulers: Plan connections that maximize usage without overloading network nodes, improving efficiency with a better-than-3 approximation guarantee.
- •For supply chain planners: Select shipments that respect capacity limits at distribution centers with improved accuracy, reducing resource waste and bottlenecks.
Authors
Michel X. Goemans, Yuchong Pan
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.