Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 30.06.2011 at 12:20 in S11, there is the following noon lecture:

The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature

Asaf Levin

Technion, Haifa, Israel

Abstract

We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are random variables with known, arbitrary distributions. These distributions depend on a common random variable $\theta$ denoting the state of the nature. We assume that if we fix a value of $\theta$, then the size variables are independent. So $\theta$ induces a limited dependency among the sizes of different items.

Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy that maximizes the expected value of items successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both nonadaptive policies (that designate a priori a fixed permutation of items to insert) and adaptive policies (that

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010