# Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 2 Nov 2025.

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

- [Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks](https://mlsanity.com/paper/1605.07990/) (2016)
- [Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints](https://mlsanity.com/paper/2006.15744/) (2020)
- [Submodular Cost Submodular Cover with an Approximate Oracle](https://mlsanity.com/paper/1908.00653/) (2019)
- [Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time](https://mlsanity.com/paper/2009.04979/) (2020)
- [On maximizing a monotone k-submodular function subject to a matroid constraint](https://mlsanity.com/paper/1607.07957/) (2016)
- [Bicriteria Approximation Algorithms for the Submodular Cover Problem](https://mlsanity.com/paper/2309.14558/) (2023)
- [Improved Approximation Algorithms for k-Submodular Function Maximization](https://mlsanity.com/paper/1502.07406/) (2015)
- [On maximizing a monotone k-submodular function under a knapsack constraint](https://mlsanity.com/paper/2105.15159/) (2021)
- [No-regret algorithms for online k-submodular maximization](https://mlsanity.com/paper/1807.04965/) (2018)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [Derandomization for k-submodular maximization](https://mlsanity.com/paper/1610.07729/) (2016)
- [Scalable Bicriteria Algorithms for the Threshold Activation Problem in Online Social Networks](https://mlsanity.com/paper/1701.08799/) (2017)

## Abstract (arXiv)

We study the k-Submodular Cover (kSC) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optimization tasks such as influence maximization, resource allocation, and sensor placement. Existing algorithms for kSC often provide weak approximation guarantees or incur prohibitively high query complexity. To overcome these limitations, we propose a textitFast Stochastic Greedy algorithm that achieves strong bicriteria approximation while substantially lowering query complexity compared to state-of-the-art methods. Our approach dramatically reduces the number of function evaluations, making it highly scalable and practical for large-scale real-world AI applications where efficiency is essential.