New Support Size Bounds and Proximity Bounds for Integer Linear Programming

Integer linear programming (ILP) is a fundamental research paradigm in algorithms. Many modern algorithms to solve structured ILPs efficiently follow one of two main approaches. The first one is to prove a small upper bound on the support size of the ILP, which is the number of variables taking non-zero values in an optimal solution, and then to only search for ILP solutions of small support. The second one is to apply an augmentation algorithm using Graver elements to an initial feasible solution obtained from a small proximity bound for the ILP, which is the distance between an optimal solution of the ILP and that of its LP relaxation. Our first contribution are new lower bounds for the support size of ILPs. Namely, we discover a connection between support sizes and an old number-theoretic conjecture by Erdős on subset-sum distinct sets. Further, we improve the previously best lower bounds on the support size of ILPs with m constraints and largest absolute value  \(\varDelta \) of any coefficient in the constraint matrix from \(\varOmega (m\log (\varDelta ))\) to \(\varOmega (m\log (\sqrt{m}\varDelta ))\) . This new lower bound asymptotically matches the best-known upper bounds. Our second contribution are new bounds on the size of Graver elements and on the proximity for ILPs. We first show nearly tight lower and upper bounds for \(g_1(A)\) , the largest 1-norm \(\Vert \boldsymbol{g}\Vert _1\) of any Graver basis element  \(\boldsymbol{g}\) of the constraint matrix A. Then we show that the proximity of any ILP in standard form with support size s is bounded by \(s\cdot c_1(A)\) , where \(c_1(A)\) is the largest 1-norm \(\Vert \boldsymbol{c}\Vert _1\) of any circuit \(\boldsymbol{c}\) of A. This improves over the known proximity bound of \(n \cdot g_1(A)\) , as s and \(c_1(A)\) can be much smaller than n and \(g_1(A)\) , respectively.