Price of Correlation in Stochastic Optimization
Speaker: | Yichuan Ding |
---|---|
Affiliation: | Stanford University |
Room: | Mathematics & Computer Building (MC) 5158 |
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.