On the complexity of dynamic submodular maximization

DOI10.1145/3519935.3519951MaRDI QIDQ6083622zbMATH OpenOpenAlexFDO

Authors

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03198

zbMATH Keywords

dynamic algorithmquery complexitysubmodular maximization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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+epsilon)$-approximate solution under a cardinality constraint, for any constant $epsilon>0$, must have an amortized query complexity that is $mathitpolynomial$ 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-epsilon)$-approximation with a $mathsfpolylog(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-epsilon$ and amortized query complexities $smashO(log(k/epsilon)/epsilo{n}^2)$ and $smash{k}^{ildeO(1/epsilo{n}^2)}logn$, respectively, where $k$ denotes the cardinality parameter or the rank of the matroid.

Cited in

(7)

• On submodular value functions and complex dynamic programming
• Fully dynamic maximal independent set with sublinear update time
• Subquadratic submodular maximization with a general matroid constraint
• Dynamic algorithms for non-monotone submodular maximization
• Dynamic algorithms for submodular maximization with a p-matchoid constraint
• Fully dynamic submodular maximization over matroids
• Dynamic algorithms for submodular matching

This page was built for publication: On the complexity of dynamic submodular maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083622)