BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250822T140000
DTEND;TZID=Asia/Kolkata:20250822T150000
DTSTAMP:20260924T000735
CREATED:20250827T082004Z
LAST-MODIFIED:20250827T082004Z
UID:1825-1755871200-1755874800@homecse.iitd.ac.in
SUMMARY:Optimal Capacity Modification for Stable Matchings with Ties by Dr. Keshav Ranjan
DESCRIPTION: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.\nSuch an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria:\n\n\n\nMINSUM: minimizing the total capacity increase across all hospitals and \nMINMAX: minimizing the maximum capacity increase for any hospital\n\nWe 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.\n\nThe 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). \nBio: 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.
URL:https://homecse.iitd.ac.in/event/optimal-capacity-modification-for-stable-matchings-with-ties-by-dr-keshav-ranjan/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR