- 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.edu – http://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.