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, July 12, 2019 — 3:30 PM EDT

Title: On the approximability of the stable matching problem with ties of size two and one-sided ties

Speaker: Kanstantsin Pashkovich
Affiliation: University of Ottawa
Room: MC 5501

Abstract:

The stable matching problem is central for game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, 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. We give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor. We also provide a tight analysis of an approximation algorithm by Huang and Kavitha for one-sided ties.

Joint work with Felix Bauckholt, Laura Sanita and Robert Chiang. 

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
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
31
1
2
3
4
5
  1. 2020 (75)
    1. August (8)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. 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 (138)
  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)