Dynamic Non-monotone Submodular Maximization
Kiarash Banihashem Leyla Biabani Samira Goudarzi MohammadTaghi Hajiaghayi Peyman Jabbarzade Morteza Monemizadeh
Maximizing submodular functions has been increasingly used in many
applications of machine learning, such as data summarization, recommendation
systems, and feature selection. Moreover, there has been a growing interest in
both submodular maximization and dynamic algorithms. In 2020, Monemizadeh and
Lattanzi, Mitrovic, Norouzi{-}Fard, Tarnawski, and Zadimoghaddam initiated
developing dynamic algorithms for the monotone submodular maximization problem
under the cardinality constraint $k$. Recently, there have been some
improvements on the topic made by Banihashem, Biabani, Goudarzi, Hajiaghayi,
Jabbarzade, and Monemizadeh. In 2022, Chen and Peng studied the complexity of
this problem and raised an important open question: "Can we extend [fully
dynamic] results (algorithm or hardness) to non-monotone submodular
maximization?". We affirmatively answer their question by demonstrating a
reduction from maximizing a non-monotone submodular function under the
cardinality constraint $k$ to maximizing a monotone submodular function under
the same constraint. Through this reduction, we obtain the first dynamic
algorithms to solve the non-monotone submodular maximization problem under the
cardinality constraint $k$. Our algorithms maintain an
$(8+\epsilon)$-approximate of the solution and use expected amortized
$O(\epsilon^{-3}k^3\log^3(n)\log(k))$ or $O(\epsilon^{-1}k^2\log^3(k))$ oracle
queries per update, respectively. Furthermore, we showcase the benefits of our
dynamic algorithm for video summarization and max-cut problems on several
real-world data sets.