DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.25

Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy Setting

Authors: Dmitry Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii, Maxim Klimenko, Dmitry Malyshev, and Stanislav Moiseev

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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).

Cite as

Dmitry Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii, Maxim Klimenko, Dmitry Malyshev, and Stanislav Moiseev. Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy Setting. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gribanov_et_al:LIPIcs.ESA.2026.25,
  author =	{Gribanov, Dmitry and Khayaleyev, Tagir and Cherniavskii, Mikhail and Klimenko, Maxim and Malyshev, Dmitry and Moiseev, Stanislav},
  title =	{{Algorithms for Standard-Form ILP Problems via Koml\'{o}s' Discrepancy Setting}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.25},
  URN =		{urn:nbn:de:0030-drops-271610},
  doi =		{10.4230/LIPIcs.ESA.2026.25},
  annote =	{Keywords: Parameterized complexity, FPT algorithms, Integer linear programming, Koml\'{o}s' conjecture, Discrepancy}
}

@InProceedings{gribanov_et_al:LIPIcs.ESA.2026.25,
  author =	{Gribanov, Dmitry and Khayaleyev, Tagir and Cherniavskii, Mikhail and Klimenko, Maxim and Malyshev, Dmitry and Moiseev, Stanislav},
  title =	{{Algorithms for Standard-Form ILP Problems via Koml\'{o}s' Discrepancy Setting}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.25},
  URN =		{urn:nbn:de:0030-drops-271610},
  doi =		{10.4230/LIPIcs.ESA.2026.25},
  annote =	{Keywords: Parameterized complexity, FPT algorithms, Integer linear programming, Koml\'{o}s' conjecture, Discrepancy}
}

Search Results

Documents authored by Malyshev, Dmitry

Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy Setting

Abstract

Cite as

Thanks for your feedback!

Could not send message