MSc THESIS DEFENCE
11.00 am, Lecture Hall 6
Rank Maximal Matching and its Variants
Sayantan Sen
Chennai Mathematical Institute.
30-05-18

---

Abstract

Graph matching has been one of the fundamental problems in graph theory. It has been studied extensively for the past three decades. In this talk we will see a variant of bipartite matching with preference namely Rank Maximality. In bipartite setting with applicants and posts, if only applicants rate posts, we can define multiple criteria of optimality. Rank Maximality is one such criteria where maximum number applicants are matched to their best rank posts and subject to that constraint maximum number of applicants are matched to their second choice posts and so on. We will see combinatorial algorithm of Irving et al which solves it via Gallai-Edmonds decomposition. We will then see an algorithm of K. Paluch of rank maximality in capacitated setting where posts have non zero capacity as an additional constraint. We will also see some results of rank maximality under manipulating applicants and an algorithm of rank maximality via randomization.