Dynamic Programming (DP): Hardness Vs. Approximation

שלחו לחבר
Nir Halman, Department of Computer Science, Princeton university
BIU Engineering Building 1103, Room 329

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.