Consistent Algorithms for Dynamic Non-Monotone Submodular Maximization with Efficient Updates

Submodular maximization is a fundamental framework for subset selection with broad applications in machine learning and data mining. In many modern applications, however, the underlying data evolves over time, making it desirable to maintain not only a high-quality solution but also a stable one that changes only slightly after each update. Recent work has initiated the study of consistent algorithms for fully dynamic submodular maximization, but existing algorithms are restricted to monotone objectives, and their expected amortized query complexity suffers from an undesirable linear dependence on the maximum number $n$ of active elements. In this paper, we address both limitations by developing ConsistentSample, a consistent algorithm for dynamic non-monotone submodular maximization under a cardinality constraint $k$. For accuracy parameter $ϵ$, our algorithm achieves a $(\frac{1}{3+2\sqrt{2}}-ϵ)$-approximation with $\mathcal{O}(\log k/{ϵ}^2)$ consistency and $\mathcal{O}\left(k^2{\log }^4\frac{k}{ϵ}+\frac{k}{{ϵ}^2}{\log }^2\frac{k}{ϵ}\right)$ expected amortized query complexity. To the best of our knowledge, among consistent algorithms for fully dynamic submodular maximization, ours is the first to achieve active-set-independent query complexity and the first to obtain a constant-factor approximation guarantee for non-monotone objectives. As a by-product, for monotone objectives, our framework achieves a $0.3178-\mathcal{O}(1/k)-ϵ$ approximation with $\mathcal{O}(\log (2/ϵ)/{ϵ}^2)$ consistency while retaining the same query complexity. We further evaluate our algorithm on the Max-Cut problem using real-world datasets, and the empirical results demonstrate its practical efficiency and stability.