The principle of optimality in the design of efficient algorithms

DOI10.1016/0022-247X(86)90147-2MaRDI QIDQ1085609zbMATH OpenOpenAlexFDO

Authors Paul Helman

Publication date 1986

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-247x(86)90147-2

zbMATH Keywords

knapsack problemNP-complete problemsstring matchingtrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Dynamic programming (90C39)

Review text

In this methodological paper, the author gives a description of applications of the dynamic programming method such as string matching, construction of optimal binary and derivation trees, knapsack problem and NP-complete problems having fully polynomial approximation schemes. The author gives a general formalism and a framework in which dynamic programming is applicable.

Recommendations

• scientific article; zbMATH DE number 579387
• scientific article; zbMATH DE number 4024619
• scientific article; zbMATH DE number 3907767
• scientific article; zbMATH DE number 6435534
• scientific article; zbMATH DE number 108385
• scientific article; zbMATH DE number 1293612
• scientific article; zbMATH DE number 3896657
• An efficient implementation of optimization algorithms
• scientific article; zbMATH DE number 49948

Cites work

• `` Strong NP-Completeness Results
• A Comprehensive Model of Dynamic Programming
• An Extension of the String-to-String Correction Problem
• Classes of discrete optimization problems and their decision problems
• Combinatorial Problems: Reductibility and Approximation
• Contribution to nonserial dynamic programming
• Dynamic programming is optimal for certain sequential decision processes
• Dynamic Programming is Optimal for Nonserial Optimization Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Finite-State Processes and Dynamic Programming
• scientific article; zbMATH DE number 3174053 (Why is no real title available?)
• scientific article; zbMATH DE number 3841211 (Why is no real title available?)
• scientific article; zbMATH DE number 3878680 (Why is no real title available?)
• scientific article; zbMATH DE number 3890770 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Minimal representations of some classes of dynamic programming
• Necessary and Sufficient Conditions for Dynamic Programming of Combinatorial Type
• On the computational power of pushdown automata
• On the optimality of algorithms for finite state sequential decision processes
• P-Complete Approximation Problems
• Recognition and parsing of context-free languages in time n3
• Solvable classes of discrete dynamic programming
• The String-to-String Correction Problem

Cited in

(8)

• \(N\) degrees of separation: Influences of dynamic programming on computer science
• The application of automated reasoning to formal models of combinatorial optimization
• Dynamic programming multi-objective combinatorial optimization
• scientific article; zbMATH DE number 4016629 (Why is no real title available?)
• Automated dynamic programming
• Dynamic programming optimization over random data: the scaling exponent for near-optimal solutions
• scientific article; zbMATH DE number 3896657 (Why is no real title available?)
• Categories, relations and dynamic programming

This page was built for publication: The principle of optimality in the design of efficient algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085609)