Fair Disaster Containment via Graph-Cut Problems

Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6321-6333, 2022.

Abstract

Graph cut problems are fundamental in combinatorial Optimization, and are a central object of study in both theory and practice. Further, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-dinitz22a, title = { Fair Disaster Containment via Graph-Cut Problems }, author = {Dinitz, Michael and Srinivasan, Aravind and Tsepenekas, Leonidas and Vullikanti, Anil}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6321--6333}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/dinitz22a/dinitz22a.pdf}, url = {https://proceedings.mlr.press/v151/dinitz22a.html}, abstract = { Graph cut problems are fundamental in combinatorial Optimization, and are a central object of study in both theory and practice. Further, 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. } }
Endnote
%0 Conference Paper %T Fair Disaster Containment via Graph-Cut Problems %A Michael Dinitz %A Aravind Srinivasan %A Leonidas Tsepenekas %A Anil Vullikanti %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-dinitz22a %I PMLR %P 6321--6333 %U https://proceedings.mlr.press/v151/dinitz22a.html %V 151 %X Graph cut problems are fundamental in combinatorial Optimization, and are a central object of study in both theory and practice. Further, 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.
APA
Dinitz, M., Srinivasan, A., Tsepenekas, L. & Vullikanti, A.. (2022). Fair Disaster Containment via Graph-Cut Problems . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6321-6333 Available from https://proceedings.mlr.press/v151/dinitz22a.html.

Related Material