Algorithms for Standard-form ILP Problems via Koml’os’ Discrepancy Setting

arXiv:2604.09806v1 Announce Type: new
Abstract: We study the standard-form ILP problem $max{ c^top x colon A x = b,; x in Z_{geq 0}^n }$, where $Ain Z^{ktimes n}$ has full row rank. We obtain refined FPT algorithms parameterized by $k$ and $Delta$, the maximum absolute value of a $ktimes k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Koml’os’ setting. Let $kappa_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(kappa_k)^{2k}Delta^2$, and the corresponding feasibility problem in time $O(kappa_k)^kDelta$. Using the best currently known bound $kappa_k=widetilde O(log^{1/4}k)$, this yields running times $O(log k)^{frac{k}{2}(1+o(1))}Delta^2$ and $O(log k)^{frac{k}{4}(1+o(1))}Delta$, respectively. Under the Koml’os conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$.