- This event has passed.
Optimal Capacity Modification for Stable Matchings with Ties by Dr. Keshav Ranjan
August 22 @ 2:00 pm - 3:00 pm
Abstract: In this talk, we consider the Hospitals/Residents (HR) problem in the presence of ties in preference lists of hospitals. Among the three notions of stability, viz. weak, strong, and super stability, we focus on strong stability. Strong stability is appealing both theoretically and practically; however, its existence is not guaranteed. Our objective is to optimally increase hospitals’ quotas so that the resulting instance admits a strongly stable matching.
Such an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria:
- MINSUM: minimizing the total capacity increase across all hospitals and
- MINMAX: minimizing the maximum capacity increase for any hospital
We prove that the MINSUM problem admits a polynomial-time algorithm, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota, the MINSUM problem becomes NP-hard, even for 0/1 costs. In fact, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching.
The talk is based on a recent work accepted at IJCAI 2025 and is a joint work with Meghana Nasre (IIT-M) and Prajakta Nimbhorkar (CMI).
Bio:
Keshav Ranjan recently (July 2025) completed his Ph.D. from the Department of Computer Science and Engineering, IIT Madras, under the supervision of Dr. Meghana Nasre. His Doctoral thesis, titled “Two-Sided Matchings: Lower Quotas, Ties, and Capacity Augmentation”, focuses on the algorithmic aspects of two-sided matching problems under various constraints. Previously, he held an M. Tech degree in Mathematics and Computing from the Department of Mathematics, IIT Patna. His research interests lie in the broad area of Graph Algorithms, with a particular focus on matching problems with preferences.