Integer Programing: An Algorithm with Exponent Linear in the Dimension

We study integer programs in standard form $\min \{{\mathbf{c}}^{\mathsf{T}}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\le \mathbf{x}\le \mathbf{u},\mathbf{x}\in {\mathbb{Z}}^n\}$, where $A\in {\mathbb{Z}}^{d\times n}$ and all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers. Let $N$ be an upper bound on the absolute values of the entries of $A$. We give a deterministic algorithm running in time $$\mathrm{poly}(L_{\mathrm{i}\mathrm{n}})+f(d)N^{O(d)}(1+\log (c_{\max }+1){)}^{O(1)},$$ where $c_{\max }$ bounds the absolute values of the costs and $L_{\mathrm{i}\mathrm{n}}$ is the input length. Prior to our work, the best known running time was $N^{O(d^2)}$ [Eisenbrand & Weismantel’20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively.