Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

DOI10.1145/3397484zbMath1499.68133OpenAlexW2962900108MaRDI QIDQ5053070

Marcin Wrochna, Dušan Knop, Michał Pilipczuk

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 programmingfixed-parameter tractabilityETH

Mathematics Subject Classification ID

Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (9)

Integer programming in parameterized complexity: five miniatures ⋮ From approximate to exact integer programming ⋮ Optimizing low dimensional functions over the integers ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Complexity of optimizing over the integers ⋮ Asymptotic behavior of Markov complexity ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

This page was built for publication: Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints