WorksComputer Science
Bounded Integer Programming in Almost Time
Abstract
We study integer programs in standard form , where , all entries of are integers, and every variable bound is finite. Let be an upper bound on the absolute values of the entries of , and one on the absolute values of the costs. For every fixed and every fixed we give a deterministic algorithm running in time where is the time to solve one linear programming relaxation exactly. Prior to our work, the best known running time for bounded variables 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, with the exponent .