Abstract
In this paper, we consider the MinimumLoad kClustering/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 > 0 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 rich literature, the minimumload objective has not been 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. [APPROX 2014, ACM Trans. Algorithms 2018]. They also show APXhardness of the problem in the plane. On the other hand, the bestknown 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]. Here the input points are partitioned into 𝓁 protected groups, and only clusters that proportionally represent each group are allowed. MLkC is the special case with 𝓁 = 1. For the fair version, we are able to obtain a randomized 3approximation algorithm in f(k,𝓁)⋅ n^O(1) time. Also, our scheme leads to an improved (1 + ε)approximation in the case of Euclidean norm with the same running time (depending also linearly on the dimension d). Our results imply the same approximations for MLkC with running time f(k)⋅ n^O(1), achieving the first constantfactor FPT approximations for this problem in general and Euclidean metric spaces.
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs.IPEC.2022.4,
author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Purohit, Nidhi and Simonov, Kirill},
title = {{FPT Approximation for Fair MinimumLoad Clustering}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {4:14:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17360},
URN = {urn:nbn:de:0030drops173600},
doi = {10.4230/LIPIcs.IPEC.2022.4},
annote = {Keywords: fair clustering, load balancing, parameterized approximation}
}
Keywords: 

fair clustering, load balancing, parameterized approximation 
Collection: 

17th International Symposium on Parameterized and Exact Computation (IPEC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 