Integer Programing: An Algorithm with Exponent Linear in the Dimension
In the authors' words
We study integer programs in standard form , where and all entries of are integers. Let be an upper bound on the absolute values of the entries of . We give a deterministic algorithm running in time \[ \operatorname{poly}(L_{\rm in})+ f(d) N^{O(d)}\bigl(1+\log(c_{\max}+1)\bigr)^{O(1)}, \] where bounds the absolute values of the costs and is the input length. Prior to our work, the best known running time was [Eisenbrand & Weismantel'20], and it has been a fundamental open problem whether the exponent can be improved to one linear in . We answer this question affirmatively.
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.