# Streaming Adaptive Submodular Maximization

arXiv: https://arxiv.org/abs/2208.08021 · HTML: https://mlsanity.com/paper/2208.08021/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 17 Aug 2022.

## Builds on (most cited first, 10 of 10)

- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and k-System Constraints](https://mlsanity.com/paper/2104.04853/) (2021)
- [Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time](https://mlsanity.com/paper/2009.04979/) (2020)
- [Combinatorial Prophet Inequalities](https://mlsanity.com/paper/1611.00665/) (2016)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Submodular Meta-Learning](https://mlsanity.com/paper/2007.05852/) (2020)
- [On Submodular Prophet Inequalities and Correlation Gap](https://mlsanity.com/paper/2107.03662/) (2021)

## Built on by (most cited first, 2 of 2)

- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies](https://mlsanity.com/paper/2404.01930/) (2024)

## Abstract (arXiv)

Many sequential decision making problems can be formulated as an adaptive submodular maximization problem. However, most of existing studies in this field focus on pool-based setting, where one can pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.