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.

Combinatorial Optimization Reading Group - Lily WangExport this event to calendar

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

Title: Popular Matchings

Speaker: Lily Wang
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

We introduce a variant of the stable matching problem on a bipartite graph G = (A [ P;E): for any node in A, from its ranking of its neighbours we can dene its ranking of matchings, which compares matchings on whether it's matched and if so, the preference order of the nodes it's matched to. The popular matching problem asks whether there is a matching M such that for every other matching M0, more nodes in A prefer M to M' than M' to M. We'll discuss the earliest known efficient algorithms for finding popular matchings over strict preference lists and in the general case with ties, and compare the complexity of the popular matching problem with the max-cardinality matching problem.

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

Waterloo, ON N2L 3G1
Canada

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 (74)
    1. August (5)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. 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)