Dynamic algorithms achieve fast updates for submodular maximization
From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids
Data Structures and Algorithms
Summary
Maximizing certain types of functions, called submodular functions, under complex rules (matroids) has many uses but can be slow when the problem size changes. The authors address this by creating an algorithm that quickly updates the solution when items are added or removed, without slowing down as the problem grows. Previous solutions' speed depended heavily on a parameter called the matroid rank, but this new method's speed depends only on logarithmic factors, making it much faster for large problems. This solves an open problem in the area of dynamic optimization algorithms.
What this means in practice
- •For advertising optimization teams: Maintain near-optimal ad campaign selections quickly as available ads and user data change over time using fast dynamic submodular maximization.
- •For network resource managers: Adaptively allocate network resources under complex constraints with fast update times when network conditions or demands evolve dynamically.
Authors
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
Abstract
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 function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.