New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

A Modification of Dynamic Programming to Reduce the Complexity / Running Time

SpeakerFrank Werner

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.