Streaming submodular maximization is a natural model for the task of
selecting a representative subset from a large-scale dataset. If datapoints
have sensitive attributes such as gender or race, it becomes important to
enforce fairness to avoid bias and discrimination. This has spurred significant
interest in developing fair machine learning algorithms. Recently, such
algorithms have been developed for monotone submodular maximization under a
cardinality constraint.
In this paper, we study the natural generalization of this problem to a
matroid constraint. We give streaming algorithms as well as impossibility
results that provide trade-offs between efficiency, quality and fairness. We
validate our findings empirically on a range of well-known real-world
applications: exemplar-based clustering, movie recommendation, and maximum
coverage in social networks.

论文研究流式子模最大化算法中公平性的应用，提出了针对劣模最大化算法的公平机器学习算法，包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后，通过社会网络中的最大覆盖，电影推荐和样本聚类等应用的实验验证了其有效性。

在 Matroid 约束下流式子模最大化中的公平性

Fairness in Streaming Submodular Maximization over a Matroid Constraint

We study the problem of extracting a small subset of representative items
from a large data stream. In many data mining and machine learning applications
such as social network analysis and recommender systems, this problem can be
formulated as maximizing a monotone submodular function subject to a
cardinality constraint $k$. In this work, we consider the setting where data
items in the stream belong to one of several disjoint groups and investigate
the optimization problem with an additional \emph{fairness} constraint that
limits selection to a given number of items from each group. We then propose
efficient algorithms for the fairness-aware variant of the streaming submodular
maximization problem. In particular, we first give a $
(\frac{1}{2}-\varepsilon) $-approximation algorithm that requires $
O(\frac{1}{\varepsilon} \log \frac{k}{\varepsilon}) $ passes over the stream
for any constant $ \varepsilon>0 $. Moreover, we give a single-pass streaming
algorithm that has the same approximation ratio of $(\frac{1}{2}-\varepsilon)$
when unlimited buffer sizes and post-processing time are permitted, and discuss
how to adapt it to more practical settings where the buffer sizes are bounded.
Finally, we demonstrate the efficiency and effectiveness of our proposed
algorithms on two real-world applications, namely \emph{maximum coverage on
large graphs} and \emph{personalized recommendation}.

本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。