{"id":"arxiv/2604.09806","url":"https://arxiv.org/abs/2604.09806","tags":["cs.DS","cs.CC","cs.CG","math.OC"],"score":0,"title":"Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined $2^{O(k)}$-analysis)","domain":"cs.DS","source":"arxiv","authors":["Dmitry Gribanov","Tagir Khayaleyev","Mikhail Cherniavskii","Maxim Klimenko","Dmitry Malyshev","Stanislav Moiseev"],"reviews":0,"subject":"cs.DS","summary":"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 $Δ$, 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)}Δ^2$, and the corresponding feasibility problem in time $2^{O(k)}Δ$. We would like to point out that the original…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}