In the context of incremental submodular maximization, we focus on maximizing submodular functions under increasing cardinality constraints and seek a good incremental solution, which is an ordering of the ground set such that each prefix of the ordering provides a good solution for its respective cardinality. A classical result indicates that the greedy algorithm achieves a competitive ratio of $\frac{\mathrm{e}}{\mathrm{e}-1} \approx 1.582$, providing an approximation guarantee across all cardinalities. No better general guarantee was previously known. We introduce an adaptive scaling algorithm that achieves a competitive ratio of $1.373$. Furthermore, we provide a deterministic lower bound of $1.25$ on the best possible competitive ratio for incremental submodular maximization.
Blogger's Review: This paper presents a significant breakthrough in incremental submodular maximization, with a new algorithm that notably improves the competitive ratio compared to the traditional greedy approach. This opens new avenues for related applications, especially in optimizing performance when dealing with large-scale datasets, where algorithm efficiency is crucial.