# Which Lp norm is the fairest? Approximations for fair facility location across all "p"

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2022.

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

- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)
- [Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2502.09724/) (2025)
- [A Fair OR-ML Framework for Resource Substitution in Large-Scale Networks](https://mlsanity.com/paper/2511.18269/) (2025)
- [Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget](https://mlsanity.com/paper/2509.00135/) (2025)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Beyond Discretization: Learning the Optimal Solution Path](https://mlsanity.com/paper/2410.14885/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Many Preferences, Few Policies: Towards Scalable Language Model Personalization](https://mlsanity.com/paper/2604.04144/) (2026)
- [Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML](https://mlsanity.com/paper/2605.06656/) (2026)

## Abstract (arXiv)

Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the Lp norm of these group distances. However, there is no clear choice of "p" in the current literature. We present a novel approach to address the challenge of choosing the right notion of fairness. We introduce the concept of portfolios, a set of solutions that contains an approximately optimal solution for each objective in a given class of objectives, such as Lp norms. This concept opens up new possibilities for getting around the "right" notion of fairness for many problems. For r client groups, we demonstrate portfolios of size Theta(log r) for the facility location and k-clustering problems, with an O(1)-approximate solution for each Lp norm. Further, motivated by the Justice40 Initiative that provides rolling budget investments, we impose a refinement-like structure on the portfolio. We develop novel approximation algorithms for these structured portfolios and show experimental evidence of their performance in two US counties. We also present a planning tool that provides potential ways to expand access to US healthcare facilities, which might be of independent interest to policymakers.