Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining
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.
Overview
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.
Presenters
Brief Biography
Mikhail Moshkov is a professor of Applied Mathematics and Computational Science (AMCS) and an affiliated professor of Computer Science (CS) at KAUST. He is also the principal investigator of the Extensions of Dynamic Programming, Machine Learning, Discrete Optimization (TREES) research group.
Professor Moshkov holds an M.S. summa cum laude in 1977 from the University of Nizhni Novgorod, Russia. He obtained his Ph.D. in 1983 from the University of Saratov, Russia, and a Doctor of Science in 1999 from Moscow State University, Russia.
Before joining KAUST, he held professorships at the University of Nizhni Novgorod, Russia, and the University of Silesia, Poland.
Moshkov received the State Scientific Stipend in Mathematics for Outstanding Scientists from April 2000 to March 2003, awarded by the Presidium of the Russian Academy of Sciences. Additionally, he received the First Degree Research Prize, awarded by the rector of the University of Silesia, Poland, in 2006.