Toward a model for backtracking and dynamic programming
DOI10.1007/S00037-011-0028-YzbMATH Open1252.68130OpenAlexW2130407580MaRDI QIDQ430838FDOQ430838
Authors: Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi 
Publication date: 26 June 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0028-y
Recommendations
- A stronger model of dynamic programming algorithms
- On exponential time lower bound of Knapsack under backtracking
- A common schema for dynamic programming and branch and bound algorithms
- Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model
- A Comprehensive Model of Dynamic Programming
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Social choice and individual values
- Introduction to algorithms
- Scheduling jobs with fixed start and end times
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Applications of approximation algorithms to cooperative games
- Some optimal inapproximability results
- Title not available (Why is that?)
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Approximating the stochastic Knapsack problem: the benefit of adaptivity
- Proving integrality gaps without knowing the linear program
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Online independent sets.
- Finite-State Processes and Dynamic Programming
- Title not available (Why is that?)
- Optimum binary search trees
- On Syntactic versus Computational Views of Approximability
- Interval selection: Applications, algorithms, and lower bounds
- Title not available (Why is that?)
- Lower bounds for polynomial calculus in the case of nonbinomial ideals.
- (Incremental) priority algorithms
- Priority algorithms for makespan minimization in the subset model.
- The power of priority algorithms for facility location and set cover
- Selecting Complementary Pairs of Literals
- Lower bounds for k-DNF resolution on random 3-CNFs
- A Comprehensive Model of Dynamic Programming
- A common schema for dynamic programming and branch and bound algorithms
- Hard Knapsack Problems
- Title not available (Why is that?)
- A stronger model of dynamic programming algorithms
- Title not available (Why is that?)
- Approximation and Online Algorithms
Cited In (26)
- A common schema for dynamic programming and branch and bound algorithms
- On exponential time lower bound of Knapsack under backtracking
- Characterizing sets of jobs that admit optimal greedy-like algorithms
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- On extensions of the deterministic online model for bipartite matching and max-sat
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Title not available (Why is that?)
- Relating models of backtracking
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Special issue in memory of Misha Alekhnovich. Foreword
- A stronger model of dynamic programming algorithms
- Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
- Dynamic backward reasoning systems
- Tensor network complexity of multilinear maps
- A Theory for Backtrack-Downweighted Walks
- Advice complexity of adaptive priority algorithms
- Backtracking problem in the traversal of an unknown directed graph by a finite robot
- Title not available (Why is that?)
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Computing (and Life) Is All about Tradeoffs
- Title not available (Why is that?)
- An exercise in transformational programming: Backtracking and Branch-and- Bound
- Limitations of incremental dynamic programming
- Models of greedy algorithms for graph problems
- Randomized priority algorithms
- Priority algorithms for graph optimization problems
This page was built for publication: Toward a model for backtracking and dynamic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q430838)
