Integer programs with m constraints are solvable in pseudo-polynomial time in $\Delta$, the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with a running time of $O(\sqrt{m}\Delta)^{2m} + O(nm)$, which improves on the state-of-the-art. Moreover, we show that improving on our algorithm for any $m$ is equivalent to improving over the quadratic time algorithm for $(\min,~+)$-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a specialized algorithm with running time $O(\sqrt{m} \Delta)^{(1 + o(1))m} + O(nm)$ for testing feasibility of an integer program and also give a tight lower bound, which is based on the SETH in this case.
翻译：带有 m 限制的整数程序在假阴时可以溶解, 以$\ Delta$, 这是限制中的最大系数, 当 m 是固定的常数 。 我们给出一种新的算法, 运行时间为$( sqrt{ m ⁇ Delta)\\% 2m} + O( nm), 这在最新工艺上有所改进 。 此外, 我们显示, 任何一百万美元的算法的改进都相当于 $( min, ⁇ ) $- convolution 的二次时间算法的改进。 这有力地证明了我们的算法运行时间是最好的。 我们还展示了一种专门算法, 运行时间为$( sqrt{m}\ Delta)\\ ( 1 + o(1)) m} + O( nm) $, 用于测试整数程序的可行性, 并且给予更窄的束缚, 以本案的 SETH 为基础 。
相关内容
微信扫码咨询专知VIP会员