Berndt, SebastianSebastianBerndtMnich, MatthiasMatthiasMnichStamm, TobiasTobiasStamm2024-04-032024-04-032024-02International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024)978-3-031-52112-6978-3-031-52113-3https://hdl.handle.net/11420/46790Integer 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 mall 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. Furthermore, we improve the previously best-known lower bounds on the support size of ILPs with m variables and largest coefficient ∆ from Ω(m log(∆)) to Ω(m log(√m∆)). 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 gmax(A), the maximal size ∥g∥1 of any Graver element g of the Graver basis of the matrix A. Finally, we show that the proximity of any ILP (A, b, c) in standard form with m constraints is bounded by m · gmax(A). Previous works proved such proximity bounds in terms of the number n of variables and gmax(A), however, m can be much smaller than n.enGraver basesInteger linear programmingproximity boundsComputer SciencesConference Paper10.1007/978-3-031-52113-3_62-s2.0-85185844264Conference Paper