Which $L_p$ norm is the fairest? Approximations for fair facility location across all "$p$"
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911925293547520 |
|---|---|
| author | Gupta, Swati Moondra, Jai Singh, Mohit |
| author_facet | Gupta, Swati Moondra, Jai Singh, Mohit |
| contents | Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the $L_p$ 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 $L_p$ 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 $Θ(\log r)$ for the facility location and $k$-clustering problems, with an $O(1)$-approximate solution for each $L_p$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_14873 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Which $L_p$ norm is the fairest? Approximations for fair facility location across all "$p$" Gupta, Swati Moondra, Jai Singh, Mohit Data Structures and Algorithms 68W25 F.2.0 Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the $L_p$ 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 $L_p$ 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 $Θ(\log r)$ for the facility location and $k$-clustering problems, with an $O(1)$-approximate solution for each $L_p$ 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. |
| title | Which $L_p$ norm is the fairest? Approximations for fair facility location across all "$p$" |
| topic | Data Structures and Algorithms 68W25 F.2.0 |
| url | https://arxiv.org/abs/2211.14873 |