CS Faculty Talks
Date: Monday, 7 October 2024
Time: 12:00 - 12:50 PM
Venue: Seminar Hall
Bipartite Matching with Fairness Constraint
Prajakta Nimbhorkar
Chennai Mathematical Institute.
07-10-2024

---

Abstract

Bipartite matching problems naturally arise in several real-world sce- narios like college admissions, allocation of residents to hospitals, advertisement- allocation for online platforms etc. In this talk, I will focus on designing algorithms for bipartite matchings when there are additional ”fairness” constraints given as input and the goal is to obtain a matching that sat- isfies all the fairness constraints. When the fairness constraints satisfy ”laminarity”, the problem is efficiently solvable whereas it is NP-hard in general. We will also see some approximation algorithms for the hard variants.