Extensions of Dynamic Programming for Combinatorial Optimization Problems (initiative project)

Extensions of Dynamic Programming Approach for Combinatorial Optimization

Details

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.