Optimization under Uncertainty: Understanding the Correlation Gap


January 11, 2011


Shipra Agrawal




When faced with the challenge of making decisions in presence of multiple uncertainties, a common simplifying heuristic is to assume independence among various sources. Although popular, the effect of this heuristic on the solution quality is little understood. In this talk, I will examine the risk associated with ignoring correlations by introducing a new concept of ‘Correlation Gap’. Correlation gap captures the price of correlations in stochastic optimization – a small correlation gap will imply that the efficient heuristic of assuming independence is actually robust against any adversarial correlations, while a large correlation will suggest that it is important to invest more in data collection and learning correlations. Additionally, I will demonstrate that the problem of bounding correlation gap appears as a fundamental question when analyzing the approximation ratios achieved by some randomized algorithmic strategies for deterministic combinatorial optimization problems. I will use function properties such as monotonicity and submodularity, and employ techniques of cross-monotonic cost-sharing schemes from game theory in a novel manner to provide a tight characterization of functions with small correlation gap. Results include small constant bounds for cost functions resulting from many popular applications such as stochastic facility location, Steiner tree network design, minimum spanning tree, single-source rent-or-buy network design etc.

Towards the end of the talk, I will briefly discuss my research on some other topics, including algorithms for online optimization and techniques for prediction market design.


Shipra Agrawal

Shipra Agrawal is a Ph.D. candidate at Department of Computer Science, Stanford University, working under the guidance of Prof. Yinyu Ye. Her primary research interests are in the areas of optimization, approximation algorithms and mathematical programming. Prior to joining Stanford, Shipra was a researcher at Bell Labs Research India, and before that a software engineer at Yahoo! India. She received her Masters in Computer Science from Indian Institute of Science, Bangalore. Her website is http://www.stanford.edu/~shipra