A Threshold Greedy Algorithm for Noisy Submodular Maximization

Wenjing Chen, Shuo Xing, Victoria G. Crawford

We consider the maximization of a submodular objective function $f:2^U\to {\mathbb{R}}_{\ge 0}$, where the objective $f$ is not accessed as a value oracle but instead subject to nois…