Tutte seminar - Yichuan Ding

Price of Correlation in Stochastic Optimization

Abstract:

Stochastic programming and robust optimization are classical methodologies for making decisions in the presence of high dimensional stochastic data. However, when only the marginal distribution is known, i.e., when the correlation information is absent, traditional stochastic or robust optimization models may not well address the problem. We can instead investigate the distributionally robust stochastic programming (DRSP) model. However, this model is NP-hard to compute. A common heuristic of computing the DRSP is to estimate only marginal distributions and then substitute a joint distribution using the independent (product) distribution. In this paper, we use techniques of cost-sharing from game theory and identify a wide class of problems for which there is only minimal loss when ignoring the correlations. It is of interest that this class includes many interesting stochastic optimization problems. For example: the stochastic uncapacitated facility location problem, and the stochastic Steiner tree problem. We find that our results also have applications for solving some classic combinatorial optimization problems such as: the well-known social welfare maximization problem, k-dimensional matching, and the transportation problem. 

This is joint work with Shipra Agarwal, Amin Saberi and Yinyu Ye.