On Integer Programming, Discrepancy, and Convolution

Abstract

Integer programs with m constraints are solvable in pseudo-polynomial time in $\Delta$, the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with a running time of $O(\sqrt{m}\Delta {)}^{2m}+O(nm)$, which improves on the state-of-the-art. Moreover, we show that improving on our algorithm for any $m$ is equivalent to improving over the quadratic time algorithm for $(\min ,+)$-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a specialized algorithm with running time $O(\sqrt{m}\Delta {)}^{(1+o(1))m}+O(nm)$ for testing feasibility of an integer program and also give a tight lower bound, which is based on the SETH in this case.

arXiv commentRevised version. A preliminary version appeared in the proceedings of ITCS 2019

Cited by in corpus (1)

• On lattice point counting in $\Delta$-modular polyhedra