Algorithms for Multistage Stochastic Optimization

Abstract. The field of stochastic optimization studies decision making under uncertainty, when only probabilistic information about the future is available. Finding approximate solutions to well-studied optimization problems (such as Steiner tree, Vertex Cover, and Facility Location, to name but a few) presents new challenges when investigated in this frame-work, which has promoted much research in approximation algorithms. There has been much interest in optimization problems in the setting of two-stage stochastic optimization with recourse, which can be para-phrased as follows: On the first day (Monday), we know a probability distribution π from which client demands will be drawn on Tuesday, and are allowed to make preliminary investments (e.g., installing links, opening facilities) towards meeting this future demand. On Tuesday, the actual requirements are revealed (drawn from the same distribution π) and we must purchase enough additional equipment to satisfy these de-mands; however, these purchases are now made at an inflated cost. I