Subset Sum in Almost-Linear Time

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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.