Spring 2020

Integer Programming and Convolution, with Applications

Thursday, February 20th, 2020 9:30 am10:30 am

Add to Calendar

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.

PDF icon presentation.pdf387.58 KB