Approximation Techniques for Stochastic Optimization Problems

In this talk we will present approximation algorithms (and general techniques) for some basic problems in the field of stochastic optimization. A canonical problem is stochastic knapsack: we are given a knapsack of size B, and a collection of items, where the items have stochastic sizes and rewards (the distributions are known in advance). The goal is to devise an algorithm (i.e., a policy which can adapt based on the realized sizes of previously inserted items) to insert the next item to maximize the expected reward of items successfully packed into the knapsack.The size and reward of the item are realized only after the item is inserted.

This basic problem can be generalized along several different directions. For example, if each of the stochastic jobs is more generally a Markov Chain (and makes random transitions each time we “play” it), we can then capture a class of (finite-horizon) multi-armed bandit problems. Or if these jobs are located at different vertices on a metric, we obtain stochastic routing and orienteering problems.

While these problems have all received much attention in fields like operations research and machine learning, the issue of their approximability has been addressed only recently. In this talk, we will present efficient approximation algorithms with near-optimal guarantees for the (general) stochastic knapsack problem, the stochastic orienteering problem, and the multi-armed bandits problem. To the best of our knowledge, prior work (and techniques) only handle very special cases of the above problems. These results are based on joint works with Anupam Gupta, Marco Molinaro, Viswanath Nagarajan, and R. Ravi, and appeared at the FOCS 2011 and SODA 2012 conferences.

Towards the end, I will also briefly discuss some of my other research in areas such as network design and scheduling. Finally, I will conclude by discussing the future directions in the above areas.