# No-regret algorithms for online k-submodular maximization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2018.

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

- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint](https://mlsanity.com/paper/2309.12025/) (2023)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)

## Abstract (arXiv)

We present a polynomial time algorithm for online maximization of k-submodular maximization. For online (nonmonotone) k-submodular maximization, our algorithm achieves a tight approximate factor in an approximate regret. For online monotone k-submodular maximization, our approximate-regret matches to the best-known approximation ratio, which is tight asymptotically as k tends to infinity. Our approach is based on the Blackwell approachability theorem and online linear optimization.