On the information-based complexity of stochastic programming

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function.