# Online and Streaming Algorithms for Constrained k-Submodular Maximization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Real-Time Bidding Benchmarking with iPinYou Dataset](https://mlsanity.com/paper/1407.7073/) (2014)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [Using Predicted Weights for Ad Delivery](https://mlsanity.com/paper/2106.01079/) (2021)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Maximizing k-Submodular Functions and Beyond](https://mlsanity.com/paper/1409.1399/) (2014)
- [On maximizing a monotone k-submodular function under a knapsack constraint](https://mlsanity.com/paper/2105.15159/) (2021)

## Abstract (arXiv)

Constrained k-submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recommendation, and many others. In many of these applications, datasets are large or decisions need to be made in an online manner, which motivates the development of efficient streaming and online algorithms. In this work, we develop single-pass streaming and online algorithms for constrained k-submodular maximization with both monotone and general (possibly non-monotone) objectives subject to cardinality and knapsack constraints. Our algorithms achieve provable constant-factor approximation guarantees which improve upon the state of the art in almost all settings. Moreover, they are combinatorial and very efficient, and have optimal space and running time. We experimentally evaluate our algorithms on instances for ad allocation and other applications, where we observe that our algorithms are efficient and scalable, and construct solutions that are comparable in value to offline greedy algorithms.