On the Optimality of Pseudo-polynomial Algorithms for Integer Programming

DOI10.4230/LIPIcs.ESA.2018.31zbMath1502.68382arXiv1607.05342OpenAlexW2963441955MaRDI QIDQ5009590

M. S. Ramanujan, Fahad Panolan, Fedor V. Fomin, Saket Saurabh

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1607.05342

zbMATH Keywords

integer programmingstrong exponential time hypothesisfine-grained complexitybranch-width of a matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Integer programming (90C10)

Related Items (4)

Unnamed Item ⋮ On Integer Programming and Convolution. ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Which problems have strongly exponential complexity?
• Integer Programming with a Fixed Number of Variables
• On the intractability of permuting a block code to minimize trellis complexity
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Minkowski's Convex Body Theorem and Integer Programming
• On the complexity of integer programming
• Constructive algorithm for path-width of matroids
• On Problems as Hard as CNF-SAT
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Dynamic Programming and Fast Matrix Multiplication
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Optimality of Pseudo-polynomial Algorithms for Integer Programming