Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Multi-parameter Approximation Schemes for APX-Hard Optimization Problems
event speaker icon
Nir Halman (Hebrew University of Jerusalem)
event date icon
Wednesday, 18.01.2017, 12:30
event location icon
Taub 201
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).