Toward a model for backtracking and dynamic programming

DOI10.1007/S00037-011-0028-YMaRDI QIDQ430838zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programminglower boundsgreedy algorithmsmodels of computation

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3606249 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 6469169 (Why is no real title available?)
• (Incremental) priority algorithms
• A Comprehensive Model of Dynamic Programming
• A Computing Procedure for Quantification Theory
• A common schema for dynamic programming and branch and bound algorithms
• A machine program for theorem-proving
• A stronger model of dynamic programming algorithms
• Applications of approximation algorithms to cooperative games
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation and Online Algorithms
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Finite-State Processes and Dynamic Programming
• Hard Knapsack Problems
• Interval selection: Applications, algorithms, and lower bounds
• Introduction to algorithms
• Lower bounds for k-DNF resolution on random 3-CNFs
• Lower bounds for polynomial calculus in the case of nonbinomial ideals.
• On Syntactic versus Computational Views of Approximability
• Online independent sets.
• Optimum binary search trees
• Priority algorithms for makespan minimization in the subset model.
• Proving integrality gaps without knowing the linear program
• Scheduling jobs with fixed start and end times
• Selecting Complementary Pairs of Literals
• Social choice and individual values
• Some optimal inapproximability results
• The power of priority algorithms for facility location and set cover
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(26)

• Models of greedy algorithms for graph problems
• scientific article; zbMATH DE number 67459 (Why is no real title available?)
• A stronger model of dynamic programming algorithms
• 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
• Randomized priority algorithms
• Lower bounds for \(k\)-DNF resolution on random 3-CNFs
• Special issue in memory of Misha Alekhnovich. Foreword
• Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
• A common schema for dynamic programming and branch and bound algorithms
• Priority algorithms for graph optimization problems
• Dynamic backward reasoning systems
• scientific article; zbMATH DE number 1086900 (Why is no real title available?)
• An exercise in transformational programming: Backtracking and Branch-and- Bound
• Tensor network complexity of multilinear maps
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Relating models of backtracking
• Limitations of incremental dynamic programming
• Computing (and Life) Is All about Tradeoffs
• scientific article; zbMATH DE number 1149402 (Why is no real title available?)
• On extensions of the deterministic online model for bipartite matching and max-sat
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• On exponential time lower bound of Knapsack under backtracking
• Characterizing sets of jobs that admit optimal greedy-like algorithms

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)