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 - Ian PostExport this event to calendar

Friday, February 1, 2013 — 3:30 PM to 4:30 PM EST

The performance of the simplex method on deterministic Markov decision processes

Speaker: Ian Post
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158

Abstract:

Motivated by the search for strongly-polynomial algorithms for linear programming (an algorithm whose runtime depends only on the number of constraints and variables, not the sizes of the numbers involved), we analyze the performance of the simplex method on Markov decision processes (MDPs), a class of LPs that is "close" to being strongly-polynomial but beyond the reach of existing techniques. We prove that for deterministic MDPs the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly-polynomial time, regardless of the discount factor of the MDP and even when each action has a distinct discount. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from one. Unlike in the discounted case the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of variables must lie and show that the simplex method always makes progress optimizing the variables in one layer.

Joint work with Yinyu Ye.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
30
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
31
1
2
3
4
5
  1. 2021 (45)
    1. May (5)
    2. April (9)
    3. March (13)
    4. February (8)
    5. 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)