The Taub Faculty of Computer Science Events and Talks

For every given real value epsilon>0, a Fully Polynomial Time Approximation Scheme (FPTAS) computes in polynomial time (in both the input size and 1/epsilon) a feasible solution that is close to the optimal solution within ratio epsilon. As epsilon can be chosen arbitrary small, and the running time is polynomial, FPTASs are considered as the “Holy grail” of approximation algorithms, but most optimization problems, e.g., strongly NP-hard problems, cannot admit an FPTAS unless P=NP. In this talk I will study several 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 circumvent the above negative results and compute for them provably near-optimal feasible solutions.

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