Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

DOI10.1145/3397484zbMath1499.68133MaRDI QIDQ5053070

Michał Pilipczuk, Marcin Wrochna, Dušan Knop

Publication date: 5 December 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3397484

zbMATH Keywords

integer linear programming; fixed-parameter tractability; ETH

Mathematics Subject Classification ID

90C10: Integer programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization