Preprint
Oct 2026
From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids
We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective f...
Kiarash Banihashem, Samira Goudarzi, M. Hajiaghayi et al.
· 0 citations