Incremental Submodular Maximization: Better Than Greedy
For researchers in submodular optimization, this provides a better algorithm and tighter bounds for a fundamental problem with applications in machine learning and combinatorial optimization.
The paper improves the competitive ratio for incremental submodular maximization from 1.582 to 1.373 using an adaptive scaling algorithm, and establishes a deterministic lower bound of 1.25.
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of $\mathrm{e}/(\mathrm{e}-1) \approx 1.582$. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of $1.373$. We complement our result by a deterministic lower bound of $1.25$ on the best possible competitive ratio for incremental submodular maximization.