Abstract :

In this talk, 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 the other side 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 p in P has a quota denoting the maximum number of applicants that can be assigned to p in an allocation of applicants to posts - referred to as a matching.

A classification for a post p is a collection of subsets of the neighbors of p. Each subset (class) has a quota denoting the maximum number of applicants from the class that can be matched top. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the posts and classes.

We consider the well-studied notion of popularity and show that a popular amongst feasible matchings (if one exists) can be computed efficiently if the classifications satisfy a certain property. To solve the classified popular matchings problem, we present a framework that involves computing max-flows iteratively in multiple flow networks.

We use the fact that, in any flow network, w.r.t. any max-flow the vertices can be decomposed into three disjoint sets and this decomposition is invariant of the flow. This simple fact turns out to be surprisingly useful in the design of our combinatorial algorithm. Besides giving polynomial-time algorithms for classified popular matching problem, our framework unifies prior algorithms from literature on popular matchings without classifications, matching the respective time complexities.

This is joint work with Prajakta Nimbhorkar and Nada Pulath.