Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting

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 $\hat{I}”$, the maximum absolute value of a $k\times k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let $\hat{I}{º}_k$ denote the maximum discrepancy over all matrices with $k$ columns whose columns have Euclidean norm at most $1$. Up to polynomial factors in the input size, the optimization problem can be solved in time $O(\hat{I}{º}_k{)}^{2k}\hat{I}{”}^2$, and the corresponding feasibility problem in time $O(\hat{I}{º}_k{)}^k\hat{I}”$. Using the best currently known bound $\hat{I}{º}_k=\tilde{O}({\log }^{1/4}k)$, this yields running times $O(\log k{)}^{\frac{k}{2}(1+o(1))}\hat{I}{”}^2$ and $O(\log k{)}^{\frac{k}{4}(1+o(1))}\hat{I}”$, respectively. Under the Komlós conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$.