Friday, June 28, 2019

Friday, June 28, 2019 — 1:00 PM EDT

Title: Approximation Algorithms for the Stable Marriage Problem

Speaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479

Abstract:

This week we will discuss stable matching when there are unacceptable pairs and preferences include ties. In this setting one can also consider the Hospitals/Residents problem and the variant where ties are one-sided.

Friday, June 28, 2019 — 3:30 PM EDT

Title: On the hardness of computing the diameter of a polytope

Speaker: Laura Sanita Affiliation: University of Waterloo Room: MC 5501

Abstract:

The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.

S M T W T F S
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. 2021 (93)
    1. October (6)
    2. September (12)
    3. August (6)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. 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)
    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)
  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)