Scholarlink

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\varDelta )^{O(m)} \text {poly}(I)\) , where \(\varDelta \) 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\varDelta )^{O(m (\log m + \log \log \varDelta ))} \text {poly}(I)\) time, that is, in almost the same time as previous dynamic programming algorithms.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Space-Efficient Algorithm for Integer Programming with Few Constraints

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Lars Rohwedder,
  • Karol Węgrzycki

摘要

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\varDelta )^{O(m)} \text {poly}(I)\) , where \(\varDelta \) 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\varDelta )^{O(m (\log m + \log \log \varDelta ))} \text {poly}(I)\) time, that is, in almost the same time as previous dynamic programming algorithms.