Title: Stochastic Knapsack Problem
| Speaker: | David Aleman |
| Affiliation: | University of Waterloo |
| Location: | MC 6029, please contact Rian Neogi for Zoo link |
Abstract: The classical NP-hard Knapsack problem takes as input a set of items with some fixed values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is less than or equal to a given limit. In this talk we will review a paper by Dean, Goemans and Vondrák, in which an stochastic variation of this problem is considered. The item values are deterministic, but now the weights of the items are independent random variables with known, arbitrary distributions. The items in the solution must be chosen sequentially, and once an item is chosen, its weight is instantiated. We will look at a couple of approximation algorithms for this problem under these settings.