Mini-batch Submodular Maximization
Its authors withdrew this paper, so there is no full text to read or summarize.
Lists
Only you see this
Abstract
We present the first *mini-batch* algorithm for maximizing a non-negative monotone *decomposable* submodular function, $F=\sum_{i=1}^N f^i$, under a set of constraints. The expected number of oracle evaluations of our algorithm only depends on the size of the ground set. Previous results require a number of oracle evaluations that either depend on $N$ or have a worst-case *exponential* dependence on the size of the ground set.
BibTeX
@misc{schwartzman2024mini,
author = {Gregory Schwartzman},
title = {{Mini-batch Submodular Maximization}},
year = {2024},
eprint = {2401.12478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2401.12478},
}