Subset sum and integer programming solved nearly in linear time
Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time
Data Structures and Algorithms
Summary
Subset Sum asks if some numbers from a list add up to a target number, and it’s long been unclear if this can be done very fast. The authors show how to solve this problem almost as fast as reading the input, which is a big step forward. They also extend this to multiple dimensions and apply it to integer programming problems with a fixed number of constraints. Their key idea is to transform sparse inputs into a form where existing fast methods work well, then carefully handle the complex boundary cases using recursion.
What this means in practice
- •For operations research teams: Test integer programming feasibility with fixed constraints faster for optimization problems involving bounded coefficients.
- •For algorithm engineers: Improve efficiency in solving subset sum and related problems in multi-dimensional integer sets using near-linear time methods.
A theory result. No direct application yet.
Authors
Lin Chen, Yuchen Mao, Guochuan Zhang
Abstract
Given an integer $t$ and a set of integers in $[N]$, Subset Sum asks whether there exists a subset that sums to $t$. A long open problem is whether Subset Sum can be solved in $O(N)$ time. We show that Subset Sum can be solved in $O(N^{1 + \varepsilon})$ time where $\varepsilon > 0$ is an arbitrarily small constant. Our result also generalizes to multi-sets in multi-dimension. That is, for any fixed $d$ and $\varepsilon >0$, the $d$-dimensional subset sum can be solved in $O(n + N^{d + \varepsilon})$ time. As an application, for any fixed $d$ and $\varepsilon$, feasibility test of integer programming with $d$ constraints can be done in $O(N^{d+\varepsilon} \mathrm{poly}(\ell_{\mathrm{in}}))$ time, where $N$ is the maximum absolute value in the constraint matrix and $\ell_{\mathrm{in}}$ is the input size. Although the algorithm is quite involved, its high-level idea is clear. It is already known that when the input set is dense and $t$ lies in the interior of the zonotope, then Subset Sum is easy to solve [Galil-Margalit '91, Bringmann-Wellnitz '21, Chen-Hu-Mao-Zhang '26]. Our key observation is that a sparse input can exhibit a dense structure when lifted to higher dimension. We show that such a lifting can be done efficiently. After lifting, the interior of the zonotope is easy to tackle, and one only needs to deal with the thin area near the boundary of the zonotope. Then we show that the boundary area can be decomposed into subproblems and solved recursively, and that there cannot be too many recursion levels since each level of recursive reduces the volume of the area significantly.