Fair Set Cover
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908327319961600 |
|---|---|
| author | Dehghankar, Mohsen Raychaudhury, Rahul Sintos, Stavros Asudeh, Abolfazl |
| author_facet | Dehghankar, Mohsen Raychaudhury, Rahul Sintos, Stavros Asudeh, Abolfazl |
| contents | The potential harms of algorithmic decisions have ignited algorithmic fairness as a central topic in computer science. One of the fundamental problems in computer science is Set Cover, which has numerous applications with societal impacts, such as assembling a small team of individuals that collectively satisfy a range of expertise requirements. However, despite its broad application spectrum and significant potential impact, set cover has yet to be studied through the lens of fairness. Therefore, in this paper, we introduce Fair Set Cover, which aims not only to cover with a minimum-size set but also to satisfy demographic parity in its selection of sets. To this end, we develop multiple versions of fair set cover, study their hardness, and devise efficient approximation algorithms for each variant. Notably, under certain assumptions, our algorithms always guarantee zero-unfairness, with only a small increase in the approximation ratio compared to regular set cover. Furthermore, our experiments on various data sets and across different settings confirm the negligible price of fairness, as (a) the output size increases only slightly (if any) and (b) the time to compute the output does not significantly increase. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11639 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fair Set Cover Dehghankar, Mohsen Raychaudhury, Rahul Sintos, Stavros Asudeh, Abolfazl Data Structures and Algorithms The potential harms of algorithmic decisions have ignited algorithmic fairness as a central topic in computer science. One of the fundamental problems in computer science is Set Cover, which has numerous applications with societal impacts, such as assembling a small team of individuals that collectively satisfy a range of expertise requirements. However, despite its broad application spectrum and significant potential impact, set cover has yet to be studied through the lens of fairness. Therefore, in this paper, we introduce Fair Set Cover, which aims not only to cover with a minimum-size set but also to satisfy demographic parity in its selection of sets. To this end, we develop multiple versions of fair set cover, study their hardness, and devise efficient approximation algorithms for each variant. Notably, under certain assumptions, our algorithms always guarantee zero-unfairness, with only a small increase in the approximation ratio compared to regular set cover. Furthermore, our experiments on various data sets and across different settings confirm the negligible price of fairness, as (a) the output size increases only slightly (if any) and (b) the time to compute the output does not significantly increase. |
| title | Fair Set Cover |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.11639 |