Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems

DOI10.1007/s00453-010-9475-0zbMath1237.90189OpenAlexW2146843586MaRDI QIDQ2428688

Agustín Bompadre

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

zbMATH Keywords

dynamic programmingcombinatorial optimization problemsmonotone arithmetic circuits

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Heuristics for vehicle routing problems: sequence or set optimization? ⋮ Limitations of incremental dynamic programming

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

This page was built for publication: Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems