Dynamic Programming (DP): Hardness Vs. Approximation

DP is both a mathematical optimization method and a computer programming method, and has found applications in numerous fields, from engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.

While many problems can be cast as dynamic programs, solving optimally these programs is NP-hard in general. For this reason, approximation algorithms are of interest.

In this talk I will present several classes of DPs for which I design approximation schemes.

This talk is based upon various works with (subsets of) Diego Klabjan, Chung-Lun Li, Mohamad Mostagir, Giacomo Nannicini, Jim Orlin and David Simchi-Levi.