Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined $2^{O(k)}$-analysis)

Abstract

We study the standard-form ILP problem $\max \{c^{\top }x:Ax=b,x\in Z_{\ge 0}^n\}$, where $A\in Z^{k\times n}$ has full row rank. We obtain refined FPT algorithms parameterized by $k$ and $\Delta$, the maximum absolute value of a $k\times k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix ${\ell }_2$-discrepancy bounds in Komlós' setting. Up to polynomial factors in the input size, the optimization problem can be solved in time $2^{O(k)}{\Delta }^2$, and the corresponding feasibility problem in time $2^{O(k)}\Delta$. We would like to point out that the original version of this work, published in ESA 2026 proceedings, contains a slightly weaker result. More precisely, the earlier bounds were $O({\kappa }_k{)}^{2k}{\Delta }^2$ for optimization and $O({\kappa }_k{)}^k\Delta$ for feasibility, where ${\kappa }_k$ denotes the maximum ${\ell }_{\infty }$-discrepancy in Komlós' setting. However, following the advice of one of the anonymous reviewers -- to whom we are very grateful -- we replaced the ${\ell }_{\infty }$-discrepancy with the ${\ell }_2$-discrepancy in the analysis. This is what allowed us to replace dependencies of the form ${\kappa }_k^{O(k)}$ with $2^{O(k)}$.