We consider the k-min-sum-radii (k-MSR) clustering problem with fairness constraints. The k-min-sum-radii problem is a mixture of the classical k-center and k-median problems. We are given a set of points P in a metric space and a number k and aim to partition the points into k clusters, each of the clusters having one designated center. The objective to minimize is the sum of the radii of the k clusters (where in k-center we would only consider the maximum radius and in k-median we would consider the sum of the individual points’ costs). Various notions of fair clustering have been introduced lately, and we follow the definitions due to Chierichetti et al. [13] which demand that cluster compositions shall follow the proportions of the input point set with respect to some given sensitive attribute. For the easier case where the sensitive attribute only has two possible values and each is equally frequent in the input, the aim is to compute a clustering where all clusters have a 1:1 ratio with respect to this attribute. We call this the 1:1 case. There has been a surge of FPT-approximation algorithms for the k-MSR problem lately, solving the problem both in the unconstrained case and in several constrained problem variants. We add to this research area by designing an FPT (6 + ϵ)-approximation that works for k-MSR under the mentioned general fairness notion. For the special 1:1 case, we improve our algorithm to achieve a (3 + ϵ)-approximation.

Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters -- especially if the data is already biased. At NIPS 2017, Chierichetti et al. proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair $k$-center problem and a $O(t)$-approximation for the fair $k$-median problem, where $t$ is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair $k$-center. We extend and improve the known results. Firstly, we give a 5-approximation for the fair $k$-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives $k$-center, $k$-supplier, $k$-median, $k$-means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed.

The $k$-center problem is a classical combinatorial optimization problem which asks to find $k$ centers such that the maximum distance of any input point in a set $P$ to its assigned center is minimized. The problem allows for elegant $2$-approximations. However, the situation becomes significantly more difficult when constraints are added to the problem. We raise the question whether general methods can be derived to turn an approximation algorithm for a clustering problem with some constraints into an approximation algorithm that respects one constraint more. Our constraint of choice is privacy: Here, we are asked to only open a center when at least $\ell$ clients will be assigned to it. We show how to combine privacy with several other constraints.