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 A is an upper hound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadiniitriou [27] 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.