Correlation Robust Stochastic Optimization

Details Correlation Robust Stochastic Optimization Correlation Robust Stochastic Optimization

2009-02-11

arxiv.org/abs/0902.1792v3

Computer Science

Data Structures and Algorithms

Scientific paper

We consider a robust model proposed by Scarf, 1958, for stochastic optimization when only the marginal probabilities of (binary) random variables are given, and the correlation between the random variables is unknown. In the robust model, the objective is to minimize expected cost against worst possible joint distribution with those marginals. We introduce the concept of correlation gap to compare this model to the stochastic optimization model that ignores correlations and minimizes expected cost under independent Bernoulli distribution. We identify a class of functions, using concepts of summable cost sharing schemes from game theory, for which the correlation gap is well-bounded and the robust model can be approximated closely by the independent distribution model. As a result, we derive efficient approximation factors for many popular cost functions, like submodular functions, facility location, and Steiner tree. As a byproduct, our analysis also yields some new results in the areas of social welfare maximization and existence of Walrasian equilibria, which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Correlation Robust Stochastic Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Correlation Robust Stochastic Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correlation Robust Stochastic Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-487032