Maximizing expected utility over a knapsack constraint

Series
ACO Student Seminar
Time
Friday, September 28, 2012 - 2:00pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jiajin Yu – College of Computing, Georgia Tech – jiajin.yu@cc.gatech.eduhttp://www.cc.gatech.edu/~jyu76/
Organizer
Cristóbal Guzmán
This work develops approximation algorithms for a stochastic knapsack problem involving an expected utility objective. The values of the items in the knapsack can only be sampled from an oracle, and the objective function is a concave function of the total value of the items in the knapsack. We will first show a polynomial number of samples is enough to approximate the true expected value close enough. Then we will present an algorithm that maximizes a class of submodular function under knapsack constraint with approximation ratio better than 1-1/e. We will also see better bounds when the concave function is a power function. At last, if time permits, we will give an FPTAS of the problem when the number of scenarios is fixed.