Maximizing expected utility over a knapsack constraint

ACO Student Seminar
Friday, September 28, 2012 - 14:00
1 hour (actually 50 minutes)
Skiles 005
College of Computing, Georgia Tech
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.