Toward a model for backtracking and dynamic programming

DOI10.1007/s00037-011-0028-yzbMath1252.68130OpenAlexW2130407580MaRDI QIDQ430838

Toniann Pitassi, Michael Alekhnovich, Avner Magen, Allan Borodin, Russell Impagliazzo, Joshua Buresh-Oppenheim

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

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Models of greedy algorithms for graph problems, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Advice complexity of adaptive priority algorithms, Special issue in memory of Misha Alekhnovich. Foreword, Lower bounds for \(k\)-DNF resolution on random 3-CNFs, On extensions of the deterministic online model for bipartite matching and max-sat, Limitations of incremental dynamic programming, On exponential time lower bound of Knapsack under backtracking, Characterizing sets of jobs that admit optimal greedy-like algorithms, A stronger model of dynamic programming algorithms, Randomized priority algorithms, Unnamed Item, Advice complexity of priority algorithms, Width, depth, and space: tradeoffs between branching and dynamic programming, Priority algorithms for graph optimization problems, Computing (and Life) Is All about Tradeoffs, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A stronger model of dynamic programming algorithms
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Scheduling jobs with fixed start and end times
• Lower bounds for polynomial calculus in the case of nonbinomial ideals.
• (Incremental) priority algorithms
• Priority algorithms for makespan minimization in the subset model.
• Online independent sets.
• The power of priority algorithms for facility location and set cover
• Optimum binary search trees
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• 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
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On Syntactic versus Computational Views of Approximability
• Interval selection: Applications, algorithms, and lower bounds
• 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
• Finite-State Processes and Dynamic Programming
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Approximation and Online Algorithms