The problem of computing a stable matching in a bipartite graph is an old and well-studied problem. Gale and Shapley showed in 1962 that such a matching always exists and can be efficiently computed. This is a classical result in algorithms with many applications in economics and computer science. Stability is a strong and rather restrictive notion. This talk will be on a relaxation of stability called ‘popularity’ and we will see simple and efficient algorithms for some popular matching problems. No background in algorithms or matching theory will be assumed.

Short Bio:

Kavitha is professor at the School of Technology and Computer Science at TIFR Mumbai and she is also the dean of our school. Prior to joining TIFR, she was a faculty at the Indian Institute of Science (Bengaluru) and a postdoc at Max-Planck Institute for Informatics, Saarbrücken. Her primary interests are in the graph algorithms and combinatorial optimisation, and has made foundational contributions in the area of graph matchings.