Adaptive Non-Monotone Threshold Sampling for Low-Adaptivity Submodular Maximization

Adaptive Non-Monotone Threshold Sampling (ADAPTIVE-NONMONOTONE-MAX and its core subroutine NON-MONOTONE-THRESHOLD-SAMPLING) is a parallel low-adaptivity algorithm for maximizing a non-negative (possibly non-monotone) submodular set function f: 2^N -> R_>=0 subject to a cardinality constraint |S| <= k, introduced by Fahrbach, Mirrokni, and Zadimoghaddam (2019). For each parallel threshold guess tau = c_1 * (1 + eps_hat)^i * Delta^* / k, NON-MONOTONE-THRESHOLD-SAMPLING (Algorithm 1) iteratively filters candidates A <- {x in A : Delta(x, S) >= tau}, terminates early if |A| < c_3 * k (ensuring every element x in N is selected with probability at most 1 / c_3), finds the largest batch size t = min{floor((1 + eps_hat)^i), |A|} via REDUCED-MEAN (Algorithm 2) on the Bernoulli indicator I_t = 1[Delta(x, S cup T) >= tau], samples T ~ U(A, min{t, k - |S|}), and applies a random-permutation post-filtering step S' <- S' cup {x_i in T : Delta(x_i, S cup {x_1, ..., x_{i-1}}) >= tau} (Lines 14-15) before updating S <- S cup T; if the loop breaks early because |A| < c_3 * k, ADAPTIVE-NONMONOTONE-MAX (Algorithm 4) runs unconstrained submodular maximization on A, uniformly downsamples to cardinality k if |U| > k, takes the highest-valued prefix U'' of a random permutation, and returns argmax_{X in {R, S', U''}} f(X).