Abstract:We study the standard-form ILP problem $\max\{ c^\top x \colon A x = b,\; x \in Z_{\geq 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 discrepancy bounds in Komlós' 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)^k\Delta$. 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ós conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$.
From: Dmitry Gribanov [view email]
[v1]
Fri, 10 Apr 2026 18:30:43 UTC (42 KB)
[v2]
Tue, 14 Apr 2026 18:56:57 UTC (42 KB)
[v3]
Sat, 18 Jul 2026 18:02:29 UTC (87 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。