DASH: Distributed Adaptive Sequencing Heuristic for Submodular Maximization

MapReduce (MR) model algorithms for maximizing monotone, submodular functions subject to a cardinality constraint (SMCC) are currently restricted to the use of the linear-adaptive (non-parallelizable) algorithm GREEDY. Low-adaptive algorithms do not satisfy the requirements of these distributed MR frameworks, thereby limiting their performance. We study the SMCC problem in a distributed setting and propose the first MR algorithms with sublinear adaptive complexity. Our algorithms, R-DASH, T-DASH and G-DASH provide ($0.316-\varepsilon$), ($0.375-\varepsilon$) and ($0.632-\varepsilon$) approximation ratio respectively with near-optimal adaptive complexity. Additionally, we provide a memory-efficient framework MED that eliminates the memory limitations of all MR model algorithms resulting from large distributed setups or considerable cardinality constraints. Finally, we provide empirical evidence to demonstrate that our sublinear-adaptive distributed algorithms provide orders of magnitude faster speedup in runtime compared to current state-of-the-art distributed algorithms while producing near identical results.