Fine-Grained Equivalence for Problems Related to Integer Linear Programming

Abstract

Integer Linear Programming with $n$ binary variables and $m$ many $0/1$-constraints can be solved in time $2^{\tilde{O}(m^2)}\text{poly}(n)$ and it is open whether the dependence on $m$ is optimal. Several seemingly unrelated problems, which include variants of Closest String, Discrepancy Minimization, Set Cover, and Set Packing, can be modelled as Integer Linear Programming with $0/1$ constraints to obtain algorithms with the same running time for a natural parameter $m$ in each of the problems. Our main result establishes through fine-grained reductions that these problems are equivalent, meaning that a $2^{O(m^{2-\epsilon })}\text{poly}(n)$ algorithm with $\epsilon >0$ for one of them implies such an algorithm for all of them. In the setting above, one can alternatively obtain an $n^{O(m)}$ time algorithm for Integer Linear Programming using a straightforward dynamic programming approach, which can be more efficient if $n$ is relatively small (e.g., subexponential in $m$). We show that this can be improved to ${n^{\prime }}^{O(m)}+O(nm)$, where $n^{\prime }$ is the number of distinct (i.e., non-symmetric) variables. This dominates both of the aforementioned running times.

17 pages