A Modification of Dynamic Programming to Reduce the Complexity / Running Time
Co-authorEvgeny Gafarov and Alexander Lazarev
We present graphical algorithms which are a modification of dynamic programming. These algorithms are also based on Bellman's recursive equations but they usually combine several states into a new one. In this way, they often reduce the running time or / and the complexity of the dynamic programming algorithm. In the talk, the focus is on such single machine problems, where in contrast to standard dynamic programming, the corresponding graphical algorithm results in a polynomial time algorithm.