Fully polynomial time $$(\Sigma ,\Pi )$$-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs

We study the nonlinear newsvendor problem concerning goods of a non-discrete nature, and a class of stochastic dynamic programs with several application areas such as supply chain management and economics. The class is characterized by continuous state and action spaces, either convex or monotone cost functions that are accessed via value oracles, and affine transition functions. We establish that these problems cannot be approximated to any degree of either relative or additive error, regardless of the scheme used. To circumvent these hardness results, we generalize the concept of fully polynomial-time approximation scheme allowing arbitrarily small additive and multiplicative error at the same time, while requiring a polynomial running time in the input size and the error parameters. We develop approximation schemes of this type for the classes of problems mentioned above. In light of our hardness results, such approximation schemes are “best possible”. A computational evaluation shows the promise of this approach.