Eastern Great Lakes Theory Workshop Talk

Approximation Algorithms for Stochastic Knapsack and Orienteering Problems

Ravishankar Krishnaswamy, Carnegie Mellon University

Saturday, September 10, 5:20-5:40pm

ABSTRACT

In the Stochastic Knapsack problem, we are given a collection of items, and each item has a known distribution over possible sizes it can assume and rewards it can fetch (these may be correlated). The goal is to place these items irrevocably into a knapsack of size B (possibly adaptively) in order to maximize the total expected reward of successful insertions. The algorithm must stop inserting items once the knapsack budget is violated (and we get no reward from the last item that caused this violation). Dean, Goemans, and Vondrak considered this problem when the rewards are independent of the sizes for each item, and gave a non-adaptive algorithm which is an O(1)-approximation to the optimal adaptive policy.

In this talk, we present an O(1)-approximation algorithm for the setting when rewards are correlated with sizes. We also briefly describe some general techniques to handle problems like stochastic orienteering (which can be thought of as stochastic knapsack where the items are now located in a metric space), and multi-armed bandits (of which the stochastic knapsack is a very special case).

Speaker Bio

Ravishankar Krishnaswamy is 5th year graduate student in the Computer Science Department, Carnegie Mellon University, pursuing his Ph.D under the advisement of Prof. Anupam Gupta. His research interests are in the areas of Approximation Algorithms, more specifically for problems in stochastic optimization, scheduling, and network design. Earlier, he completed his B.Tech from the Department of Computer Science and Engineering, IIT Madras in 2007.

< Schedule < EaGL-IV homepage