Development of mathematical and algorithmic foundations for
extensions of dynamic programming
approach for combinatorial optimization problems that allow usual
dynamic programming approach
(counting the number of optimal solutions, multi-stage
optimization, construction of the set of Pareto optimal points, and study of
relationships between two cost functions). Experimental study of known problems
such as shortest paths in graphs, search trees, sequence alignment, matrix
chain multiplication, etc.