License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.4
URN: urn:nbn:de:0030-drops-173600
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17360/
Bandyapadhyay, Sayan ;
Fomin, Fedor V. ;
Golovach, Petr A. ;
Purohit, Nidhi ;
Simonov, Kirill
FPT Approximation for Fair Minimum-Load Clustering
Abstract
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 > 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 minimum-load 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 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]. 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 3-approximation 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 constant-factor 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 Minimum-Load Clustering}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {4:1--4:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17360},
URN = {urn:nbn:de:0030-drops-173600},
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 |
