Events by date

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.