Double Greedy Algorithm for Unconstrained Non-Monotone Submodular Maximization

The Double Greedy algorithm is a single-pass linear-time algorithmic framework for Unconstrained Submodular Maximization (USM) of a non-negative (possibly non-monotone) submodular function f: 2^N -> R_+ over an n-element ground set N = {u_1, ..., u_n}, introduced and analyzed by Buchbinder, Feldman, Naor, and Schwartz (2012/2015). The algorithm maintains two nested candidate sets X_i subseteq Y_i initialized to X_0 = emptyset and Y_0 = N (corresponding to a correlated greedy execution on f and its complement f_bar(S) = f(N \ S)). In each step i = 1, ..., n, it evaluates the marginal gain of adding u_i to the growing solution, a_i = f(X_{i-1} + u_i) - f(X_{i-1}), and the marginal gain of removing u_i from the shrinking solution, b_i = f(Y_{i-1} - u_i) - f(Y_{i-1}), which satisfy a_i + b_i >= 0 by submodularity (Lemma 2.1). The deterministic variant (Algorithm 1) adds u_i to X_{i-1} if a_i >= b_i and removes u_i from Y_{i-1} otherwise, whereas the randomized variant (Algorithm 2) sets a_i' = max{a_i, 0} and b_i' = max{b_i, 0} and includes u_i (setting X_i = X_{i-1} + u_i, Y_i = Y_{i-1}) with probability a_i' / (a_i' + b_i') and excludes u_i (setting X_i = X_{i-1}, Y_i = Y_{i-1} - u_i) with probability b_i' / (a_i' + b_i'), terminating with X_n = Y_n after 2n value-oracle queries.