A common schema for dynamic programming and branch and bound algorithms

DOI10.1145/58562.59304zbMath0676.68058OpenAlexW1984503189MaRDI QIDQ3832081

Paul Helman

Publication date: 1989

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/58562.59304

zbMATH Keywords

dynamic programmingcombinatorial optimizationbranch-and-boundparallel algorithmscomplexity analysissearch strategiesformal models of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Discrete mathematics in relation to computer science (68R99)

Related Items (9)

Categories, relations and dynamic programming ⋮ A general framework for enumerating equivalence classes of solutions ⋮ Toward a model for backtracking and dynamic programming ⋮ Limitations of incremental dynamic programming ⋮ A stronger model of dynamic programming algorithms ⋮ Branch and Win: OR tree search algorithms for solving combinatorial optimisation problems. ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Sufficient and necessary conditions for solution finding in valuation-based systems ⋮ The application of automated reasoning to formal models of combinatorial optimization

This page was built for publication: A common schema for dynamic programming and branch and bound algorithms