Fair Submodular Cover
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916315288043520 |
|---|---|
| author | Chen, Wenjing Xing, Shuo Zhou, Samson Crawford, Victoria G. |
| author_facet | Chen, Wenjing Xing, Shuo Zhou, Samson Crawford, Victoria G. |
| contents | Submodular optimization is a fundamental problem with many applications in machine learning, often involving decision-making over datasets with sensitive attributes such as gender or age. In such settings, it is often desirable to produce a diverse solution set that is fairly distributed with respect to these attributes. Motivated by this, we initiate the study of Fair Submodular Cover (FSC), where given a ground set $U$, a monotone submodular function $f:2^U\to\mathbb{R}_{\ge 0}$, a threshold $τ$, the goal is to find a balanced subset of $S$ with minimum cardinality such that $f(S)\geτ$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(\frac{1}ε, 1-O(ε))$. We then present a continuous algorithm that achieves a $(\ln\frac{1}ε, 1-O(ε))$-bicriteria approximation ratio, which matches the best approximation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with a number of empirical evaluations that demonstrate the effectiveness of our algorithms on instances of maximum coverage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04804 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fair Submodular Cover Chen, Wenjing Xing, Shuo Zhou, Samson Crawford, Victoria G. Machine Learning Computers and Society Data Structures and Algorithms Submodular optimization is a fundamental problem with many applications in machine learning, often involving decision-making over datasets with sensitive attributes such as gender or age. In such settings, it is often desirable to produce a diverse solution set that is fairly distributed with respect to these attributes. Motivated by this, we initiate the study of Fair Submodular Cover (FSC), where given a ground set $U$, a monotone submodular function $f:2^U\to\mathbb{R}_{\ge 0}$, a threshold $τ$, the goal is to find a balanced subset of $S$ with minimum cardinality such that $f(S)\geτ$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(\frac{1}ε, 1-O(ε))$. We then present a continuous algorithm that achieves a $(\ln\frac{1}ε, 1-O(ε))$-bicriteria approximation ratio, which matches the best approximation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with a number of empirical evaluations that demonstrate the effectiveness of our algorithms on instances of maximum coverage. |
| title | Fair Submodular Cover |
| topic | Machine Learning Computers and Society Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.04804 |