Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time

We give an $O_{d,\epsilon }(n+N^{d+\epsilon })$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N{]}^d$, for every fixed $d$ and $\epsilon >0$. This directly implies an $O_{d,\epsilon }(n+N^{d+\epsilon })$-time algorithm for feasibility test of integer programming. Prior to our work, the best-known algorithm has a running time of $O_d(n+N^{O(d^2)})$ [Eisenbrand, Weismantel’19]. Specifically, if $d=1$, our algorithm runs in $O_{\epsilon }(n+N^{1+\epsilon })$-time for the standard subset sum problem, which is near-linear in the largest input integer. Prior to our work, subset sum can be solved in time near-linear in the target $t$ [Bringmann’17], or near-linear in the mixed parameter $\sqrt{Nt}$ [Chen, Lian, Mao, Zhang’24]. It is a fundamental open problem whether the algorithm can be made near-linear in $N$, which is settled affirmatively in this paper up to an arbitrary small $N^{\epsilon }$ term.