Fair Maximization of Monotone Submodular Functions in Data Streams
摘要
Streaming fair submodular maximization is attracting considerable research interest due to its broad applications in machine learning, particularly for tasks such as feature selection and text summary against large-scale data and fairness considerations. Given a sequence of data points belonging to distinct groups and arriving in a streaming manner, the problem aims to select k data points from the stream to maximize the total revenue of the selected points. In this paper, we first devise an efficient \((\frac{1}{2}-\varepsilon )\) -approximation algorithm with \(O(\log (\frac{1}{\varepsilon }\log \frac{k}{\varepsilon }))\) passes, an improvement over the previous \(O(\frac{1}{\varepsilon }\log \frac{k}{\varepsilon })\) passes. Then, we present a \(\left( \frac{1}{3} - \varepsilon \right) \) -approximation algorithm that needs only one pass and consumes a buffer of size \(O(k+|B|)\) and achieves a ratio strictly greater than \(\frac{1}{4}\) while using a buffer of size \(O(k\log k)\) . Lastly, we conduct extensive experiments using real-world datasets to validate our method, demonstrating that it outperforms all state-of-the-art algorithms in terms of efficiency, effectiveness, and scalability.