On Integer Programming and Convolution
share
Integer programs with a fixed number of constraints can be solved in pseudo-polynomial time. We present a surprisingly simple algorithm and matching conditional lower bounds. Consider an IP in standard form {c^T x : A x = b, x∈ Z^n_> 0}, where A∈ Z^m× n, b∈ Z^m and c∈ Z^n. Let Δ be an upper bound on the absolute values in A. We show that this IP can be solved in time O(mΔ)^2m·( b _∞). The previous best algorithm has a running time of n· O(mΔ)^2m· b _1^2. The hardness of (min, +)-convolution has been used to prove conditional lower bounds on a number of polynomially solvable problems. We show that improving our algorithm for IPs of any fixed number of constraints is equivalent to improving (min, +)-convolution. More precisely, for any fixed m there exists an algorithm for solving IPs with m constraints in time O(m(Δ + b _∞))^2m-δ for some δ > 0, if and only if there is a truly sub-quadratic algorithm for (min, +)-convolution. For the feasibility problem, where the IP has no objective function, we improve the running time to O(mΔ)^m(Δ) (Δ + b _∞). We also give a matching lower bound here: For every fixed m and δ > 0 there is no algorithm for testing feasibility of IPs with m constraints in time n^O(1)· O(m(Δ + b _∞))^m - δ unless the SETH is false.
READ FULL TEXT