Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with O*(2^k) edges, whose weights are integers of the order of O*(2^k). To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges, which may be of independent interest.
Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant 2 in the base of the exponent cannot be further improved for Vector Bin Packing.
Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints.

Joint work with Alexandra Lassota and Adam Polak. It will appear on ICALP 2022.