On Integer Programming, Discrepancy, and Convolution
Klaus Jansen, Lars Rohwedder
Abstract
Integer programs with a fixed number of constraints are solvable in pseudo-polynomial time in the largest coefficient of any constraint. We give a new algorithm which improves the running time of the state of the art. Moreover, we show that improving on our algorithm for any number of constraints is equivalent to improving over the quadratic time algorithm for (min, +)-convolution. This is strong evidence that our algorithm’s running time is the best possible. We also present a specialized algorithm for testing the feasibility of an integer program and give a tight lower bound, which is based on the strong exponential time hypothesis in this case. Funding: This work was supported by the German Research Foundation [Grants JA 612/16-1, JA 612/20-1].