  


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 knapsackconstrained 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 11/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. Download: [PDF] Entry Submitted: 10/22/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  