# Fair Disaster Containment via Graph-Cut Problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination](https://mlsanity.com/paper/1408.6491/) (2014)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [A Lottery Model for Center-type Problems With Outliers](https://mlsanity.com/paper/1710.00287/) (2017)

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

- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Fair Correlation Clustering in Forests](https://mlsanity.com/paper/2302.11295/) (2023)

## Abstract (arXiv)

Graph cut problems are fundamental in Combinatorial Optimization, and are a central object of study in both theory and practice. Furthermore, the study of fairness in Algorithmic Design and Machine Learning has recently received significant attention, with many different notions proposed and analyzed for a variety of contexts. In this paper we initiate the study of fairness for graph cut problems by giving the first fair definitions for them, and subsequently we demonstrate appropriate algorithmic techniques that yield a rigorous theoretical analysis. Specifically, we incorporate two different notions of fairness, namely demographic and probabilistic individual fairness, in a particular cut problem that models disaster containment scenarios. Our results include a variety of approximation algorithms with provable theoretical guarantees.