Space-Efficient Algorithm for Integer Programming with Few Constraints
<|reference_start|>Space-Efficient Algorithm for Integer Programming with Few Constraints: Integer linear programs $\min\{c^T x : A x = b, x \in \mathbb{Z}^n_{\ge 0}\}$, 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\Delta)^{O(m)} \text{poly}(I)$, where $\Delta$ 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\Delta)^{O(m (\log m + \log\log\Delta))} \text{poly}(I)$ time, that is, in almost the same time as previous dynamic programming algorithms.<|reference_end|>
@article{rohwedder2024space-efficient,
    title={Space-Efficient Algorithm for Integer Programming with Few Constraints},
    author={Lars Rohwedder, Karol Wk{e}grzycki},
    journal={arXiv preprint arXiv:2409.03681},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.03681},
    primaryClass={cs.DS}
}