Matroids, Matchings and Fairness

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Sergei VassilvitskiiZenodo 2021 · DOI

Abstract

The need for fairness in machine learning algorithms is increasingly critical. A recent focus has been on developing fair versions of classical algorithms, such as those for bandit learning, regression, and clustering. We extend this line of work to include algorithms for optimization subject to one or multiple matroid constraints. We map out this problem space, showing optimal solutions, approximation algorithms, or hardness results depending on the specific problem flavor. Our algorithms are efficient and empirical experiments demonstrate that fairness is achievable without a large compromise to the overall objective.
BibTeX
@inproceedings{chierichetti2021matroids,
  author = {Flavio Chierichetti and Ravi Kumar and Silvio Lattanzi and Sergei Vassilvitskii},
  title = {{Matroids, Matchings and Fairness}},
  booktitle = {Zenodo},
  year = {2021},
  doi = {10.5281/zenodo.4697719},
}

Loading related content...

Figure