TY - CONF
T1 - Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
Y1 - 2011
A1 - Li,Jian
A1 - Deshpande, Amol
KW - Approximation algorithms
KW - Approximation methods
KW - combinatorial problems
KW - Fourier series
KW - knapsack problems
KW - optimisation
KW - OPTIMIZATION
KW - polynomial approximation
KW - polynomial time approximation algorithm
KW - Polynomials
KW - Random variables
KW - stochastic combinatorial optimization
KW - stochastic knapsack
KW - stochastic shortest path
KW - stochastic spanning tree
KW - vectors
AB - We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error ϵ for any ϵ >; 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.
JA - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE
SN - 978-1-4577-1843-4
M3 - 10.1109/FOCS.2011.33
ER -