Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining - 2021
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. We developed 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 the bi-criteria optimization problem, and (v) to study the 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.
Overview
Abstract
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. We developed 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 the bi-criteria optimization problem, and (v) to study the 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.
Brief Biography
Mikhail Moshkov is a professor in the CEMSE Division at King Abdullah University of Science and Technology, Saudi Arabia since October 1, 2008. He earned a master's degree from Nizhni Novgorod State University, received his doctorate from Saratov State University, and habilitation from Moscow State University. From 1977 to 2004, Dr. Moshkov was with Nizhni Novgorod State University. Since 2003 he worked in Poland at the Institute of Computer Science, University of Silesia, and since 2006 also in the Katowice Institute of Information Technologies. His main areas of research are the complexity of algorithms, combinatorial optimization, and data mining. Dr. Moshkov is author or co-author of eight research monographs published by Springer.
