2026-08-25T18:47:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27161 2026-08-25T13:18:16Z ddc:004 open_access

Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy Setting Gribanov, Dmitry Khayaleyev, Tagir Cherniavskii, Mikhail Klimenko, Maxim Malyshev, Dmitry Moiseev, Stanislav Parameterized complexity FPT algorithms Integer linear programming Komlós' conjecture Discrepancy We study the standard-form ILP problem c^⊤ x → max Ax = b, x ∈ ℤ_{≥ 0}ⁿ, where A ∈ ℤ^{k× 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} Δ², and the corresponding feasibility problem in time O(κ_k)^kΔ. Using the best currently known bound κ_k = Õ(log^{1/4}k), this yields running times O(log k)^{k/2(1+o(1))} Δ² 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 2^O(k). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Gribanov and Tagir Khayaleyev and Mikhail Cherniavskii and Maxim Klimenko and Dmitry Malyshev and Stanislav Moiseev 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.25 urn:nbn:de:0030-drops-271610 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode