Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
From MaRDI portal
Publication:2428688
DOI10.1007/s00453-010-9475-0zbMath1237.90189MaRDI QIDQ2428688
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9475-0
90C27: Combinatorial optimization
90C39: Dynamic programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Limitations of incremental dynamic programming, Heuristics for vehicle routing problems: sequence or set optimization?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a model for backtracking and dynamic programming
- A stronger model of dynamic programming algorithms
- The complexity of computing the permanent
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- (Incremental) priority algorithms
- Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems
- Computing Powers in Parallel
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Approximations of Dynamic Programs, I
- Approximations of Dynamic Programs, II
- Using Randomization to Break the Curse of Dimensionality
- Lower bounds for resolution and cutting plane proofs and monotone computations
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Trivial integer programs unsolvable by branch-and-bound
- A survey of computational complexity results in systems and control
