# Tight FPT Approximation for Constrained k-Center and k-Supplier

arXiv: https://arxiv.org/abs/2110.14242 · HTML: https://mlsanity.com/paper/2110.14242/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 56 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 14 of 14)

- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [KFC: A Scalable Approximation Algorithm for k-center Fair Clustering](https://mlsanity.com/paper/2010.13949/) (2020)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers](https://mlsanity.com/paper/1608.01700/) (2016)
- [Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)](https://mlsanity.com/paper/1910.11850/) (2019)
- [FPT Approximation for Constrained Metric k-Median/Means](https://mlsanity.com/paper/2007.11773/) (2020)
- [Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs](https://mlsanity.com/paper/1605.02530/) (2016)
- [Capacitated Center Problems with Two-Sided Bounds and Outliers](https://mlsanity.com/paper/1702.07435/) (2017)
- [Constant Factor Approximation for Capacitated k-Center with Outliers](https://mlsanity.com/paper/1401.2874/) (2014)
- [Balanced k-Center Clustering When k Is A Constant](https://mlsanity.com/paper/1704.02515/) (2017)

## Built on by (most cited first, 4 of 4)

- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)
- [Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering](https://mlsanity.com/paper/2609.06384/) (2026)

## Abstract (arXiv)

In this work, we study a range of constrained versions of the k-supplier and k-center problems such as: capacitated, fault-tolerant, fair, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [SODA 2015] in context of the k-median and k-means objectives. In this work, we extend this framework to the k-supplier and k-center objectives. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k-supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, ℓ-diversity, and fair k-supplier problems, with and without outliers. We obtain the following results: We give 3 and 2 approximation algorithms for the constrained k-supplier and k-center problems, respectively, with mathsfFPT running time kO(k) · nO(1), where n = |C cup L|. Moreover, these approximation guarantees are tight; that is, for any constant ε>0, no algorithm can achieve (3-ε) and (2-ε) approximation guarantees for the constrained k-supplier and k-center problems in mathsfFPT time, assuming mathsfFPT neq mathsfW[2]. Furthermore, we study these constrained problems in outlier setting. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k-supplier and k-center problems, respectively, with mathsfFPT running time (k+m)O(k) · nO(1), where n = |C cup L| and m is the number of outliers.