University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Yichuan DingExport this event to calendar

Friday, June 24, 2011 — 3:30 PM to 4:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2020 (114)
    1. December (1)
    2. November (11)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)