تقرير
Fairness in Submodular Maximization over a Matroid Constraint
| العنوان: | Fairness in Submodular Maximization over a Matroid Constraint |
|---|---|
| المؤلفون: | Halabi, Marwa El, Tarnawski, Jakub, Norouzi-Fard, Ashkan, Vuong, Thuy-Duong |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Computers and Society, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, Mathematics - Optimization and Control |
| الوصف: | Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.14299 |
| رقم الأكسشن: | edsarx.2312.14299 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |