Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Friday, July 12, 2019 1:00 PM EDT
Title: A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
Speaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479Abstract:
We will continue the discussion of stable matching when there are unacceptable pairs and one-sided ties. Two weeks ago, we looked at a 3/2-approximation that was purely combinatorial.
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 5501Abstract:
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.