Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining

NOTE - The lecture starts at 2 p.m. sharp
 

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
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.

This work was done jointly with Hassan AbouEisha, Talha Amin, Igor Chikalov,
and Shahid Hussain