Skip to content

Dynamic Non-Submodular Maximization Over Cardinality and Matroid Constraints

Nov 2026 · International Journal of Foundations of Computer Science · 0 citations

Abstract

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.