FPT Approximation for Fair Minimum-Load Clustering
share
In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k that denotes the number of clusters. Additionally, we are given a set F of cluster centers in the same metric space. The goal is to select a set C⊆ F of k centers and assign each point in P to a center in C, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have a rich literature, the minimum-load objective is not studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [ACM Trans. Algo. 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is O(k), even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017], which generalizes MLkC. Here the input points are colored by one of the ℓ colors denoting the group they belong to. MLkC is the special case with ℓ=1. Considering this problem, we are able to obtain a 3-approximation in f(k,ℓ)· n^O(1) time. Also, our scheme leads to an improved (1 + ϵ)-approximation in case of Euclidean norm, and in this case, the running time depends only polynomially on the dimension d. Our results imply the same approximations for MLkC with running time f(k)· n^O(1), achieving the first constant approximations for this problem in general and Euclidean metric spaces.
READ FULL TEXT