Fairness and Explainability in Clustering Problems

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the algorithms and machine learning communities. In general, we are given a metric space and the task is to find a specified number of clusters to minimize some objective involving the centers of the clusters.

Our first problem is the colorful k-center problem. In the classic k-center with outliers problem, the objective is to minimize the maximum distance from any point to its nearest center, while a given number of points can be omitted from contributing to the maximum. That is, these points are not served by any center. Colorful k-center is a generalization of this problem. Instead of only serving enough points, each point belongs to some color class and a certain number of points of each color are required to be served in a solution. When this problem was first introduced by [Ban+19], a pseudo-approximation using k + omega - 1 centers was given for general metric spaces where omega is the number of color classes. We give the first true approximation algorithm with k centers that gives a 3-approximation for colorful k-center.

Next, we present our progress on the non-uniform k-center problem (NUkC or t-NUkC). In NUkC, we are given pairs (ki, ri), 1