Dynamic Non-Submodular Maximization Over Cardinality and Matroid Constraints

Dynamic submodular maximization tackles the challenge of maintaining approximate solutions for evolving datasets, where elements are inserted or deleted over time. Unlike static or streaming models, this setting requires efficiently updating the solution after each data modification without reprocessing the entire dataset, ensuring responsiveness to real-time changes. A key challenge lies in balancing strong approximation guarantees with low amortized update time, as traditional greedy approaches become computationally prohibitive under frequent updates. This framework prioritizes time efficiency over space complexity, reflecting modern computational demands in applications like renewable energy systems, real-time summarization, recommendation systems, and adaptive clustering. [Formula: see text]Our work investigates the dynamic maximization of a monotone non-submodular function [Formula: see text] over a ground set [Formula: see text] of size [Formula: see text] under cardinality and matroid constraints. For the cardinality constraint [Formula: see text] (a positive integer), we present a randomized algorithm that with high probability maintains an [Formula: see text]-approximation solution with [Formula: see text] amortized update time, where [Formula: see text] denotes the generic submodularity ratio introduced by Gong et al. [21]. For the matroid constraint [Formula: see text] of rank [Formula: see text], we propose an algorithm achieving a [Formula: see text]-approximation for any [Formula: see text] with [Formula: see text] amortized update time.