Parallel Greedy Submodular Maximization in Logarithmic Adaptivity and Nearly-Linear Time via Poly-Logarithmic Batch Filtering

Parallel Greedy Submodular Maximization in Logarithmic Adaptivity and Nearly-Linear Time is a randomized parallel value-oracle algorithm introduced by Ene and Nguyen (2018, 2019) for maximizing a monotone non-negative submodular function f : 2^V -> R_{>=0} subject to a cardinality constraint |S| <= k. Operating over O(1/epsilon) outer phases (each increasing f(S) by at least epsilon*M/100) and O(ln n / epsilon) inner iterations per phase with block size ell = epsilon^2 * k / (100 ln n), the algorithm samples only m = O((ln n)^2 / epsilon^4) random subsets R_1, ..., R_m ~ U(U_t, ell): if max_j f(R_j | S) >= (1 - 10*epsilon)*(ell/k)*(M - Old), it adds R_max to S; otherwise it draws Theta(ln n / epsilon) batches of m random subsets, selects a batch i satisfying avg_i <= (1 - 8*epsilon)*(ell/k)*(M - Old) and sum_{e in U_t} v_{i,e} <= |U_t|*(1 - 8*epsilon)*(M - Old)/k, and filters out U_t^- = {e in U_t : v_{i,e} < (1 - 7*epsilon)*(M - Old)/k}, achieving a (1 - 1/e - O(epsilon)) approximation in O(ln n / epsilon^2) adaptive rounds and O(n poly(log n, 1/epsilon)) total oracle queries.