Space-Efficient Algorithm for Integer Programming with Few Constraints

Abstract

Integer linear programs $\min \{c^{T}x:Ax=b,x\in {\mathbb{Z}}_{\ge 0}^n\}$, where $A\in {\mathbb{Z}}^{m\times n}$, $b\in {\mathbb{Z}}^m$, and $c\in {\mathbb{Z}}^n$, can be solved in pseudopolynomial time for any fixed number of constraints $m=O(1)$. More precisely, in time $(m\hat{I}”{)}^{O(m)}\text{poly}(I)$, where $\hat{I}”$ is the maximum absolute value of an entry in $A$ and $I$ the input size. Known algorithms rely heavily on dynamic programming, which leads to a space complexity of similar order of magnitude as the running time. In this paper, we present a polynomial space algorithm that solves integer linear programs in $(m\hat{I}”{)}^{O(m(\log m+\log \log \hat{I}”))}\text{poly}(I)$ time, that is, in almost the same time as previous dynamic programming algorithms.

9 pages