Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

We consider integer programming problems in standard form $\max {c^Tx : Ax = b, , x\geq 0, , x \in Z^n}$where$A \in Z^{m \times n}$,$b \in Z^m$and$c \in Z^n$\mathrm{.}Weshowthatsuchanintegerprogramcanbesolvedintime$(m \Delta)^{O(m)} \cdot |b|_\infty^2$,where$\Delta$ is an upper bound on each absolute value of an entry in $A$. This improves upon the longstanding best bound of Papadimitriou (1981) of $(m\cdot \mathrm{\Delta }{)}^{O(m^2)}$, where in addition, the absolute values of the entries of $b$ also need to be bounded by $\mathrm{\Delta }$. Our result relies on a lemma of Steinitz that states that a set of vectors in $R^m$ that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by $m$. We also use the Steinitz lemma to show that the ${\mathrm{\ell }}_1$-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by $m\cdot (2m\cdot \mathrm{\Delta }+1{)}^m$. Here $\mathrm{\Delta }$ is again an upper bound on the absolute values of the entries of $A$. The novel strength of our bound is that it is independent of $n$. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.