Optimization Online


Maximizing expected utility over a knapsack constraint

Jiajin Yu (jiajin.yu***at***cc.gatech.edu)
Ahmed Shabbir (sahmed***at***isye.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.

Download: [PDF]

Entry Submitted: 10/22/2012
Entry Accepted: 10/22/2012
Entry Last Modified: 08/12/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society