Price of Correlations in Stochastic Optimization

Shipra Agrawal (), Yichuan Ding (), Amin Saberi () and Yinyu Ye ()
Additional contact information
Shipra Agrawal: Department of Computer Science, Stanford University, Stanford, California 94305
Yichuan Ding: Department of Management Science and Engineering, Stanford University, Stanford, California 94305
Amin Saberi: Department of Management Science and Engineering, Stanford University, Stanford, California 94305
Yinyu Ye: Department of Management Science and Engineering, Stanford University, Stanford, California 94305

Operations Research, 2012, vol. 60, issue 1, 150-162

Abstract: When decisions are made in the presence of high-dimensional stochastic data, handling joint distribution of correlated random variables can present a formidable task, both in terms of sampling and estimation as well as algorithmic complexity. A common heuristic is to estimate only marginal distributions and substitute joint distribution by independent (product) distribution. In this paper, we study possible loss incurred on ignoring correlations through a distributionally robust stochastic programming model, and we quantify that loss as price of correlations (POC). Using techniques of cost sharing from game theory, we identify a wide class of problems for which POC has a small upper bound. To our interest, this class will include many stochastic convex programs, uncapacitated facility location, Steiner tree, and submodular functions, suggesting that the intuitive approach of assuming independent distribution acceptably approximates the robust model for these stochastic optimization problems. Additionally, we demonstrate hardness of bounding POC via examples of subadditive and supermodular functions that have large POC. We find that our results are also useful for solving many deterministic optimization problems like welfare maximization, k -dimensional matching, and transportation problems, under certain conditions.

Keywords: stochastic optimization; submodularity; cost sharing; correlation gap; joint distributions (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.1011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:1:p:150-162

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().