On the complexity of dynamic submodular maximization

We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of n insertions and deletions. We show that any algorithm that maintains a (0.5 + ǫ)-approximate solution under a cardinality constraint, for any constant ǫ > 0, must have an amortized query complexity that is polynomial in n. Moreover, a linear amortized query complexity is needed in order to maintain a 0.584-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMNF + 20, Mon20] that achieve (0.5ǫ)-approximation with a polylog(n) amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee 1 -1/eǫ and amortized query complexities O(log(k/ǫ)/ǫ 2 ) and k O(1/ǫ 2 ) log n, respectively, where k denotes the cardinality parameter or the rank of the matroid.