Subset sum problem solved faster with nearly linear time algorithm
Subset Sum in Almost-Linear Time
Data Structures and Algorithms
Summary
The subset sum problem asks if some numbers from a list add up exactly to a target number. The authors present a new computer algorithm that finds such subsets much faster than before, especially when numbers are not too large. They use recent mathematical insights and advanced geometric covering techniques to achieve this speed. This improvement means computers can solve these problems more efficiently in many practical scenarios.
What this means in practice
- •For cryptography engineers: Enhance cryptographic schemes relying on subset sum hardness by understanding faster algorithms for related problems.
- •For operations research teams: Speed up optimization tasks that involve subset selection with exact sum constraints in logistics or resource allocation.
A theory result. No direct application yet.
Authors
Ce Jin, Xiao Mao
Abstract
We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le Δ$ that sums to the target $t$ in $\mathcal{O}(n+Δ^{1+o(1)})$ time. This improves upon the previous $\widetilde{\mathcal{O}}(n + Δ^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $Δ$ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.