Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Preprint
Abstract
Maximizing a monotone submodular function under cardinality constraint $k$ is a core problem in machine learning and database with many basic applications, including video and data summarization, recommendation systems, feature extraction, exemplar clustering, and coverage problems. We study this classic problem in the fully dynamic model where a stream of insertions and deletions of elements of an underlying ground set is given and the goal is to maintain an approximate solution using a fast update time. A recent paper at NeurIPS'20 by Lattanzi, Mitrovic, Norouzi{-}Fard, Tarnawski, Zadimoghaddam claims to obtain a dynamic algorithm for this problem with a $\frac{1}{2} -ε$ approximation ratio and a query complexity bounded by $\mathrm{poly}(\log(n),\log(k),ε^{-1})$. However, as we explain in this paper, the analysis has some important gaps. Having a dynamic algorithm for the problem with polylogarithmic update time is even more important in light of a recent result by Chen and Peng at STOC'22 who show a matching lower bound for the problem -- any randomized algorithm with a $\frac{1}{2}+ε$ approximation ratio must have an amortized query complexity that is polynomial in $n$. In this paper, we develop a simpler algorithm for the problem that maintains a $(\frac{1}{2}-ε)$-approximate solution for submodular maximization under cardinality constraint $k$ using a polylogarithmic amortized update time.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Adaptive submodular inverse reinforcement learning for spatial search and map explorationAutonomous Robots, 2022
- Deterministic Dynamic Matching in O(1) Update TimeAlgorithmica, 2019
- An Efficient Greedy Algorithm for Sequence Recommendation2019
- Better Streaming Algorithms for the Maximum Coverage ProblemTheory of Computing Systems, 2018
- An exemplar-based approach to individualized parcellation reveals the need for sex specific functional networksNeuroImage, 2018
- Near-optimal probabilistic search via submodularity and sparse regressionAutonomous Robots, 2015
- Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designsDiscrete Applied Mathematics, 2013
- THE INSPECTION PARADOXProbability in the Engineering and Informational Sciences, 2003
- Generalized submodular cover problems and applicationsTheoretical Computer Science, 2001
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978