On the Reducibility of Submodular Functions
  The scalability of submodular optimization methods is critical for their
usability in practice. In this paper, we study the reducibility of submodular
functions, a property that enables us to reduce the solution space of
submodular optimization problems without performance loss. We introduce the
concept of reducibility using marginal gains. Then we show that by adding
perturbation, we can endow irreducible functions with reducibility, based on
which we propose the perturbation-reduction optimization framework. Our
theoretical analysis proves that given the perturbation scales, the
reducibility gain could be computed, and the performance loss has additive
upper bounds. We further conduct empirical studies and the results demonstrate
that our proposed framework significantly accelerates existing optimization
methods for irreducible submodular functions with a cost of only small
performance losses.
