Title: A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete ListsSpeaker: Madison Van Dyk Affiliation: University of Waterloo Room: MC 5479
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.
Title: On the approximability of the stable matching problem with ties of size two and one-sided tiesSpeaker: Kanstantsin Pashkovich Affiliation: University of Ottawa Room: MC 5501
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.