A new book - "Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining" by Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, and Mikhail Moshkov - was recently published by Springer: https://link.springer.com/book/10.1007/978-3-319-91839-6
Dynamic programming is an efficient technique to solve optimization problems. It is based on decomposing the initial problem into simpler ones and solving these sub-problems beginning from the simplest ones. A conventional dynamic programming algorithm returns an optimal object from a given set of objects.
The aim of this book is to develop extensions of dynamic programming which allow us (i) to describe the set of objects under consideration; (ii) to perform a multi-stage optimization of objects relative to different criteria; (iii) to count the number of optimal objects; (iv) to find the set of Pareto optimal points for bi-criteria optimization problem; and (v) to study relationships between two criteria.
The considered applications include optimization of decision trees and decision rule systems as algorithms for problem solving, as ways for knowledge representation, and as classifiers; optimization of element partition trees for rectangular meshes which are used in finite element methods for solving PDEs; and multi-stage optimization for such classic combinatorial optimization problems as matrix chain multiplication, binary search trees, global sequence alignment, and shortest paths.
The results presented in this book can be useful for researchers in combinatorial optimization, data mining, knowledge discovery, machine learning, and finite element methods, especially for those who are working in rough set theory, test theory, logical analysis of data, and PDE solvers. This book can be used in the creation of courses for graduate students.