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, June 21, 2019 1:00 PM EDT
Title: Maximum Cardinality Popular Matchings
Speaker: Ishan Bansal Affiliation: University of Waterloo Room: MC 5479Abstract:
We have seen the algorithm by Abraham, Irving, Kavitha, and Mehlhorn which deals with finding popular matchings (can be easily modified to give maximum cardinality popular matchings) in bipartite graphs with one-sided preference lists.
Friday, June 21, 2019 3:30 PM EDT
Title: Finding perfect matchings in random regular graphs in linear expected time
Speaker: Michael Anastos Affiliation: Carnegie Mellon University Room: MC 5501Abstract:
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results suggest that the first algorithm is superior.