Toward a model for backtracking and dynamic programming
type: Item
instance of: scholarly article
title: Toward a model for backtracking and dynamic programming
zbMATH Open document ID: 1252.68130
author: Michael Alekhnovich
author: Allan Borodin
author: Joshua Buresh-Oppenheim
author: Russell Impagliazzo
author: Avner Magen
author: Toniann Pitassi
published in: Computational Complexity
publication date: 2012-06-26T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 6050359
zbMATH Keywords: greedy algorithms
zbMATH Keywords: dynamic programming
zbMATH Keywords: models of computation
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: s00037-011-0028-y
OpenAlex ID: W2130407580
cites work: Lower bounds for k-DNF resolution on random 3-CNFs
cites work: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
cites work: Lower bounds for polynomial calculus in the case of nonbinomial ideals.
cites work: The power of priority algorithms for facility location and set cover
cites work: Scheduling jobs with fixed start and end times
cites work: Q3002764
cites work: Social choice and individual values
cites work: (Incremental) priority algorithms
cites work: Approximation and Online Algorithms
cites work: A stronger model of dynamic programming algorithms
cites work: Hard Knapsack Problems
cites work: Q4375756
cites work: Introduction to algorithms
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: Q5501284
cites work: Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
cites work: Interval selection: Applications, algorithms, and lower bounds
cites work: Q4375757
cites work: Online independent sets.
cites work: Some optimal inapproximability results
cites work: A common schema for dynamic programming and branch and bound algorithms
cites work: A Comprehensive Model of Dynamic Programming
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Selecting Complementary Pairs of Literals
cites work: Finite-State Processes and Dynamic Programming
cites work: On Syntactic versus Computational Views of Approximability
cites work: Optimum binary search trees
cites work: Q4171868
cites work: Q4856179
cites work: Priority algorithms for makespan minimization in the subset model.
cites work: Applications of approximation algorithms to cooperative games
cites work: When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
DOI: 10.1007/S00037-011-0028-Y
description: scientific article; zbMATH DE number 6050359