Fine-Grained Equivalence for Problems Related to Integer Linear Programming
<|reference_start|>Fine-Grained Equivalence for Problems Related to Integer Linear Programming: 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-\varepsilon})} \text{poly}(n)$ algorithm with $\varepsilon > 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'}^{O(m)} + O(nm)$, where $n'$ is the number of distinct (i.e., non-symmetric) variables. This dominates both of the aforementioned running times.<|reference_end|>
@article{rohwedder2024fine-grained,
    title={Fine-Grained Equivalence for Problems Related to Integer Linear
  Programming},
    author={Lars Rohwedder, Karol Wk{e}grzycki},
    journal={arXiv preprint arXiv:2409.03675},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.03675},
    primaryClass={cs.DS cs.CC}
}