# FPT Approximation for Fair Minimum-Load Clustering

@article{Bandyapadhyay2021FPTAF, title={FPT Approximation for Fair Minimum-Load Clustering}, author={Sayan Bandyapadhyay and F. Fomin and Petr A. Golovach and Nidhi Purohit and Kirill Simonov}, journal={ArXiv}, year={2021}, volume={abs/2107.09481} }

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… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 37 REFERENCES

A constant-factor approximation algorithm for the k-median problem (extended abstract)

- Computer Science
- STOC '99
- 1999

This work presents the first constant-factor approximation algorithm for the metric k-median problem, a polynomial-time algorithm that finds a feasible solution of objective function value within a factor of 6 of the optimum, and gives constant factor approximation algorithms for several natural extensions of the problem. Expand

Faster Algorithms for the Constrained k-means Problem

- Mathematics, Computer Science
- Theory of Computing Systems
- 2017

An upper bound is shown on ℓ by giving a randomized algorithm that outputs a list of 2Õ(k/ε)$2^{\tilde {O} (k/\varepsilon )}$k-centers and a closely matching lower bound is given of 2Ω~( k/ε), which is a significant improvement over the previous result of Ding and Xu (2015. Expand

A local search approximation algorithm for k-means clustering

- Computer Science, Mathematics
- SCG '02
- 2002

This work considers the question of whether there exists a simple and practical approximation algorithm for k-means clustering, and presents a local improvement heuristic based on swapping centers in and out that yields a (9+ε)-approximation algorithm. Expand

Approximation Algorithms for Minimum-Load k-Facility Location

- Computer Science
- ACM Trans. Algorithms
- 2018

The main result is the first polytime approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric), and it is proved that MLk FL is strongly NP-hard on line metric. Expand

Optimal algorithms for approximate clustering

- Mathematics, Computer Science
- STOC '88
- 1988

This work gives a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1 for a fixed cluster size. Expand

Approximation Algorithms for Socially Fair Clustering

- Computer Science, Mathematics
- COLT
- 2021

This work introduces a strengthened LP relaxation and shows that it has an integrality gap of Θ( log l log log l ) for a fixed p, and presents a bicriteria approximation algorithm, which generalizes the bicritical approximation of Abbasi et al. (2021). Expand

On the Fixed-Parameter Tractability of Capacitated Clustering

- Mathematics, Computer Science
- ICALP
- 2019

A (1 + )-approximation algorithm is given for Euclidean inputs of arbitrary dimension for capacitated k-median and k-means problems parameterized by the number of centers with similar running time. Expand

Clustering without Over-Representation

- Computer Science
- KDD
- 2019

This paper obtains an algorithm that has provable guarantees of performance and a simpler combinatorial algorithm for the special case of the problem where no color has an absolute majority in any cluster. Expand

Fair Algorithms for Clustering

- Computer Science, Mathematics
- NeurIPS
- 2019

This work significantly generalizes the seminal work of Chierichetti this http URL and transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. Expand

Fair k-Center Clustering for Data Summarization

- Computer Science, Mathematics
- ICML
- 2019

This paper provides a simple approximation algorithm for the $k$-center problem under the fairness constraint with running time linear in the size of the data set and $k$. Expand