On the optimality of pseudo-polynomial algorithms for integer programming
From MaRDI portal
Publication:2687057
DOI10.1007/s10107-022-01783-xOpenAlexW2884971091MaRDI QIDQ2687057
Saket Saurabh, Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan
Publication date: 1 March 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-022-01783-x
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Integer programming (90C10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. X: Obstructions to tree-decomposition
- Which problems have strongly exponential complexity?
- On a class of \(O(n^ 2)\) problems in computational geometry
- 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 Integer Programming and Convolution.
- 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
This page was built for publication: On the optimality of pseudo-polynomial algorithms for integer programming
