# A Center in Your Neighborhood: Fairness in Facility Location

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2019.

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

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Fair Wasserstein Coresets](https://mlsanity.com/paper/2311.05436/) (2023)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [Exploring Rawlsian Fairness for K-Means Clustering](https://mlsanity.com/paper/2205.02052/) (2022)
- [Sanitized Clustering against Confounding Bias](https://mlsanity.com/paper/2311.01252/) (2023)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [Linear Programming based Approximation to Individually Fair k-Clustering with Outliers](https://mlsanity.com/paper/2412.10923/) (2024)
- [Bicriteria Approximation Algorithms for Priority Matroid Median](https://mlsanity.com/paper/2210.01888/) (2022)
- [Can Evolutionary Clustering Have Theoretical Guarantees?](https://mlsanity.com/paper/2212.01771/) (2022)
- [Optimization of the location and design of urban green spaces](https://mlsanity.com/paper/2303.07202/) (2023)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)

## Abstract (arXiv)

When selecting locations for a set of facilities, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that takes local population densities into account. In particular, given k facilities to locate and a population of size n, we define the "neighborhood radius" of an individual i as the minimum radius of a ball centered at i that contains at least n/k individuals. Our objective is to ensure that each individual has a facility within at most a small constant factor of her neighborhood radius. We present several theoretical results: We show that optimizing this factor is NP-hard; we give an approximation algorithm that guarantees a factor of at most 2 in all metric spaces; and we prove matching lower bounds in some metric spaces. We apply a variant of this algorithm to real-world address data, showing that it is quite different from standard clustering algorithms and outperforms them on our objective function and balances the load between facilities more evenly.