2018/03/13 by Klaus Jansen, Jansen, Klaus, Lars Rohwedder +1 · 2 citations
Engineering · #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1803.04744
Integer programs with m constraints are solvable in pseudo-polynomial time in Δ, the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with a running time of O(√(m)Δ)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(√(m) Δ)(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.