arXiv · Oct 19, 2026
Integer Programing: An Algorithm with Exponent Linear in the Dimension
By Lin Chen, Yuchen Mao, Guochuan Zhang
We study integer programs in standard form min{c^Tx:Ax=b, lleqxlequ, xinZⁿ}, where AinZ^(d× n) and all entries of b,c,l,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 [ poly(L_in)+ f(d) N^{O(d)}(1+log(c_{max}+1))^{O(1)}, ] where cmax bounds the absolute values of the costs and L_in 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²) can be improved to one linear in d. We answer this question affirmatively.