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 - David ShmoysExport this event to calendar

Friday, April 4, 2008 — 3:30 PM to 4:30 PM EDT

Approximation algorithms for (two) discrete stochastic optimization problems

Speaker: David Shmoys
Affiliation: Cornell University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

One of the most active areas of research in the design of approximation algorithms is for discrete stochastic optimization problems, with a particular focus on 2-stage problems with recourse. Here, we are given a probability distribution over inputs, and the aim is to find a feasible solution that minimizes the expected cost of the solution found (with respect to the input distribution); an approximation algorithm finds a solution that is guaranteed to be nearly optimal. Techniques initially developed in the context of deterministic approximation, including rounding approaches, primal-dual algorithms, and randomization, have proved to be important in this context as well. We will focus on two specific examples, the a priori traveling salesman problem and a 2-stage stochastic single-machine scheduling problem, and for each, we will give an algorithm that is guaranteed to find a solution within a constant factor of optimal.

This is joint work with Mauro Sozio and Kunal Talwar.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
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
  1. 2021 (57)
    1. June (10)
    2. May (7)
    3. April (9)
    4. March (13)
    5. February (8)
    6. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    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)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)