Monday, November 26th, 2012 | 4:00pm-5:00pm | Burnside 1205 |

Department of Computer Science, Carnegie Mellon University

Approximation Algorithms for Stochastic Knapsack and Multi-Armed Bandits

In the stochastic knapsack problem, we are given a knapsack with size B, and a set of jobs whose sizes and rewards are drawn from a known probability distribution. However, the only way to know the actual size and reward is to schedule the job---when it completes, we get to know these values. How should we schedule jobs to maximize the expected total reward? What if the job sizes and rewards are correlated? What if we are allowed to preempt or cancel jobs once they have been scheduled? In this talk we will discuss a constant-factor approximation algorithm for these stochastic knapsack problems. It is based on a time-indexed linear programming relaxation for the problems. This approach extends to give, using a more interesting rounding scheme, a constant factor approximation algorithm for some budgeted multi-armed bandit problems. This is joint work with Ravishankar Krishnaswamy, Marco Molinaro, and R.Ravi, all from CMU. Paper available on the arXiv.