Maximizing expected utility over a knapsack constraint
Jiajin Yu (jiajin.yucc.gatech.edu)
Abstract: The expected utility knapsack problem is to pick a set of items whose values are described by random variables so as to maximize the expected utility of the total value of the items picked while satisfying a constraint on the total weight of items picked. We consider the following solution approach for this problem: (i) use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular maximization problem, and then (ii) use an approximation algorithm on the deterministic counterpart. We show that a polynomial number of samples is enough for a deterministic approximation that is close in relative error. Then, exploiting the strict monotonicity of typical utility functions, we present an algorithm that maximizes an increasing submodular function over a knapsack constraint with approximation ratio better than 1-1/e. For power utility functions we provide explicit approximation ratios leading to a polynomial time approximation algorithm. Assuming that the random values are completely described by a fixed and finite set of realizations, we also give a fully polynomial approximation scheme (FPTAS) for the expected utility knapsack problem with power utilities.
Keywords: Knapsack problem, Utility maximization, Submodularity, Sample Average Approximation, Approximation algorithm
Category 1: Combinatorial Optimization (Approximation Algorithms )
Category 2: Stochastic Programming
Category 3: Integer Programming (Other )
Citation: Technical Report, ISyE, Georgia Tech, August 12, 2014.
Entry Submitted: 10/22/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|