"Approximation Algorithms for Fair Clustering"
Ali Vakilian (TTIC)
Monday, May 17th 2021, 2-3pm
Abstract:
Growing use of automated machine learning in high-stake decision making tasks has led to an extensive line of research on the societal aspects of algorithms. In particular, the design of fair algorithms for the task of clustering, which is a core problem in both machine learning and algorithms, has received lots of attention in recent years. The fair clustering problem was first introduced in the seminal work of (Chierichetti, Kumar, Lattanzi and Vassilvitskii, 2017) where they proposed the “proportionality/balance inside the clusters” as the notion of fairness. Since then, fairness in clustering has been advanced in this setting and has been further studied in other contexts such as equitable representation and individual fairness.
In this talk, I will overview my recent works on the design of efficient approximation algorithms for fair clustering in the three aforementioned contexts. My talk is based on three papers co-authored with Arturs Backurs, Piotr Indyk, Sepideh Mahabadi, Yury Makarychev, Krzysztof Onak, Baruch Schieber, Tal Wagner.