Speaker: Dr. Nir Halman, Hebrew Univerisity

Title: Multi-parameter approximation schemes for hard Newsvendor problems

Abstract: For every given real value e>0, a Fully Polynomial Time Approximation Scheme (FPTAS) computes in polynomial time (in both the input size and 1/e) a feasible solution that is close to the optimal solution within ratio e. As e can be chosen arbitrary small, and the running time is polynomial, FPTASs are considered as the “Holy grail” of approximation algorithms.

In this talk I will study 3 hard variants of the classical newsvendor problem, each of which cannot admit an FPTAS. However, by expanding the notion of FPTASs to multi-parameter approximation schemes, it is possible to compute for them provably near-optimal feasible solutions. 

The talk is based upon 3 papers by (a subset of) Nir Halman (HUJI), Giacomo Nannicini (SUTD), Jim Orlin (MIT) and David Simchi-Levi  (MIT)