2026/04/10 by Dmitry Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii +3
#cs.DS #cs.CC #cs.CG #math.OC
We study the standard-form ILP problem max\ c^\top x \colon A x = b, x ∈ Z≥ 0n \, where A∈ Zk× n has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k× k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κ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(κk)2kΔ2, and the corresponding feasibility problem in time O(κk)kΔ. Using the best currently known bound κk=\widetilde O(log1/4k), this yields running times O(log k)(k)/(2)(1+o(1))Δ2 and O(log k)(k)/(4)(1+o(1))Δ, respectively. Under the Komlós conjecture, the dependence on k in both running times reduces to 2O(k).