Approximation Algorithms for Fair Clustering

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 all of the three aforementioned contexts. My talk is based on two papers co-authored with Arturs Backurs, Piotr Indyk, Yury Makarychev, Krzysztof Onak, Baruch Schieber, Tal Wagner.

Bio. Ali Vakilian is a postdoctoral researcher at the IDEAL institute hosted by TTIC. His research interests include learning-based algorithms, algorithmic fairness, algorithms for massive data and combinatorial optimization. Ali received his PhD from MIT under the supervision of Erik Demaine and Piotr Indyk.