PhD Defense: On Algorithmic Fairness and Stochastic Models for Combinatorial Optimization and Unsupervised Machine Learning

Leonidas Tsepenekas
10.17.2022 14:30 to 16:30

IRB 4107

Combinatorial optimization and unsupervised machine learning problems have been extensively studiedand are relatively well-understood. Examples of such problems that play a central role in our work areclustering problems and problems of finding cuts in graphs. The goal of the research to be presentedwas to introduce novel variants of the aforementioned problems, by generalizing their classic variantsinto two, not necessarily disjoint, directions. The first direction involves incorporating fairness aspects toa problem's specifications, and the second involves the introduction of some form of randomness in theproblem definition.Fairness in the design of algorithms and in machine learning has received a significant amount ofattention during the last few years, mainly due to the realization that standard optimization approachescan frequently lead to severely unfair outcomes, that can potentially hurt the individuals or the groupsinvolved in the corresponding application. As far as considerations of fairness are concerned, we willbegin by presenting two novel individually-fair clustering models, together with algorithms withprovable guarantees for them. The first such model exploits randomness in order to provide fairsolutions, while the second is purely deterministic. The high-level motivation behind both of them istrying to treat similar individuals similarly. Moving forward, we focus on a graph cut problem thatcaptures situations of disaster containment in a network. For this problem we introduce two novel fairvariants. The first variant focuses on demographic fairness, while the second considers a probabilisticnotion of individual fairness. Again, we will demonstrate algorithms with provable guarantees for thenewly introduced variants.In the next part of the presentation, we turn our attention to generalizing problems through theintroduction of stochasticity. At first, we present algorithmic results for a computational epidemiologyproblem, whose goal is to control the stochastic diffusion of a disease in a contact network. Thisproblem can be interpreted as a stochastic generalization of a static graph cut problem. Finally, we willdiscuss a well-known paradigm in stochastic optimization, namely the two-stage stochastic setting withrecourse. Two-stage problems capture a wide variety of applications revolving around the trade-offbetween provisioning and rapid response. In this setting, we present a family of clustering problems thathad not yet been studied in the literature, and for this family we show novel algorithmic techniques thatprovide constant factor approximation algorithms.We conclude with a discussion on open problems and future research directions in the general area ofalgorithmic fairness.

Examining Committee


Dr. Aravind Srinivasan

Dean’s Representative:

Dr. Shuvra S. Bhattacharyya


Dr. John P. Dickerson

Dr. Hal Daume

Dr. Leonidas Lampropoulos

Dr. Ravi Kumar