RandGreeDi and NMRandGreeDi Randomized Distributed Submodular Maximization under Hereditary Constraints

RandGreeDi and NMRandGreeDi are two-round randomized distributed MapReduce algorithms introduced by Barbosa, Ene, Nguyen, and Ward (2015) for maximizing monotone and non-monotone non-negative submodular functions f : 2^V -> R_{>=0} subject to any hereditary constraint family I subseteq 2^V (including cardinality, matroid, knapsack, and p-system constraints). In Round 1, each element e in V is assigned independently and uniformly at random to one of m machines (forming V_i ~ V(1/m)), and each machine i runs the standard greedy algorithm Greedy(V_i) to produce S_i (or two sequential disjoint greedy runs S_i^1 = Greedy(V_i) and S_i^2 = Greedy(V_i \ S_i^1) in NMRandGreeDi); in Round 2, a single reducer collects S = union_i S_i (or union_i (S_i^1 union S_i^2)), runs a beta-approximation algorithm Alg(S) to obtain T, and returns the best solution among T and all Round 1 machine solutions.