Talks
Spring 2020

# Integer Programming and Convolution, with Applications

Thursday, Feb. 20, 2020 9:30 am10:30 am PST

Integer programs (IP) with $m$ constraints are solvable in pseudo-polynomial time. We give a new algorithm based on the Steinitz Lemma and dynamic programming with a better pseudo-polynomial running time than previous results. Vectors $v_1,\ldots,v_n$ in $R^m$ that sum up to the $0$ vector can be seen as a circle in $R^m$ that walks from $0$ to $v_1$ to $v_1 + v_2$, etc. until it reaches $v_1 + \ldots + v_n = 0$ again. The Steinitz Lemma says that if each of the vectors is small with respect to some norm, we can reorder the vectors in a way that each point in the circle is not far away from $0$ w.r.t. the same norm. We show in the talk that a solution to the IP $\max c^T x, A x = b, x >= 0, x in Z^n$ can be found in time $O(m \Delta)^{2m} log(||b||_\infty) + O(nm)$ where $\Delta$ is the biggest absolute value of any entry in $A$. Moreover, we establish a strong connection to the problem $(min,+)$-convolution. $(min,+)$-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved signi?cantly. We show that further improvements to our pseudo-polynomial algorithm for any ?xed number $m$ of constraints are equivalent to improvements for $(min,+)$-convolution. This is a strong evidence that our algorithm?s running time is best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints. Our algorithm for the feasibility problem runs in $O(m \Delta)^{m}\log(\Delta) \log(\Delta + ||b||_\infty) + O(nm)$. Finally we show for the feasibility problem also a tight lower bound, which is based on the Strong Exponential Time Hypothesis (SETH), and give some applications for knapsack and scheduling problems. This is joint work with Lars Rohwedder.