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 Colloquium - Kanstantsin PashkovichExport this event to calendar

Friday, June 4, 2021 — 3:30 PM EDT

Title: On the approximability of the maximum cardinality stable matching problem with ties  

Speaker: Kanstantsin Pashkovich
Affliliation: University of Waterloo
Zoom: Contact Emma Watson

Abstract:

The maximum cardinality stable matching problem is central in game theory. When participants are allowed to have ties in their preferences, the problem of finding a stable matching of maximum cardinality is NP-hard, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. For the general case, i.e., for the case of ties of size at most L, we develop a new algorithm with approximation factor (3L-2)/(2L -1). Interestingly, our approximation factor matches the integrality gap for the case of ties of size at most L. Also in case when L equals 2, our result matches the known UGC-hardness result.   We will also discuss the potential for improving the best known UGC-hardness result for the maximum cardinality stable matching problem.

 

Event tags 

S M T W T F S
29
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
  1. 2021 (85)
    1. October (1)
    2. September (8)
    3. August (7)
    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)
  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)