PhD Proposal: Probabilistic notions of Fairness for problems in Combinatorial Optimization
Sharmila Duppala
Monday, May 20, 2024, 3:00-4:30 pm 
Abstract
Classical Combinatorial Optimization problems such as graph matching, set covering, set packing, and clustering have been extensively studied for over half a century and are relatively well-understood. Recently, there has been growing emphasis on integrating fairness considerations into these classical problems, spurred by several recent studies on discrimination by existing unfair algorithms. This has given rise to a new field known as algorithmic fairness, wherein various fundamental problems are studied under varying notions of fairness.
My proposed research focuses on incorporating a probabilistic notion of fairness into these NP-Hard problems. We will begin the talk by motivating our probabilistic notion of fairness. Subsequently, we will introduce proportional fairness, a widely studied notion of group fairness. Then we discuss incorporating this notion into problems such as Graph Matching and Set Packing, and present our algorithms with provable guarantees. Following this, we will introduce fair variants of a set cover problem aiming to capture both group and individual fairness simultaneously. We will then present our algorithms for multiple variants of this problem. Finally, we will talk about open problems and future research directions within the general area of algorithmic fairness.
My proposed research focuses on incorporating a probabilistic notion of fairness into these NP-Hard problems. We will begin the talk by motivating our probabilistic notion of fairness. Subsequently, we will introduce proportional fairness, a widely studied notion of group fairness. Then we discuss incorporating this notion into problems such as Graph Matching and Set Packing, and present our algorithms with provable guarantees. Following this, we will introduce fair variants of a set cover problem aiming to capture both group and individual fairness simultaneously. We will then present our algorithms for multiple variants of this problem. Finally, we will talk about open problems and future research directions within the general area of algorithmic fairness.
Bio
Sharmila Duppala is a PhD student at the University of Maryland, College Park. She is co-advised by professors Aravind Srinivasan and John P. Dickerson. Sharmila's research interests include probabilistic relaxations of fairness in combinatorial problems. Specifically, she is interested in studying the algorithmic challenges of incorporating "acceptable" and "meaningful" notions of fairness into problems like Clustering, Graph Matching, and Set Covering & Packing problems. Furthermore, she studies the role of randomness in providing fairness in problems that are otherwise intractable.
This talk is organized by Migo Gui