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

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time (m.Delta)(O(m)) .parallel to b parallel to(2)(infinity), 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 . Delta)(O(m2)), where in addition, the absolute values of the entries of b also need to be bounded by 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.