| Title | : | Optimal Matchings under Classifications |
| Speaker | : | Nada Abdul Majeed Pulath (IITM) |
| Details | : | Mon, 28 Jan, 2019 2:30 PM @ A M Turing Hall |
| Abstract: | : | In this work, we consider the problem of computing an optimal matching in a bipartite graph
where elements of one side of the bipartition specify preferences over the other side, and one or both sides can have capacities and classifications. The input instance is a bipartite graph G=(A U P,E), where A is a set of applicants, P is a set of posts, and each applicant ranks its neighbors in an order of preference, possibly involving ties. Moreover, each vertex v in A U P has a quota q(v) denoting the maximum number of
partners it can have in any allocation of applicants to posts - referred to as a matching.
A classification for a vertex u is a collection of subsets of neighbors of u. Each subset (class) has an upper quota denoting the maximum number of vertices from the class that can be matched to u.
The goal is to find a matching that is optimal amongst all the feasible matchings,
which are matchings that respect quotas of all the vertices and classes.
We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in G with maximum number of rank-1 edges, subject to that, maximum number of rank-2 edges and so on. We present an O(|E|^2)-time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We show an analogous result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one. |
