DASH: Distributed Adaptive Sequencing Heuristic for Submodular Maximization. (arXiv:2206.09563v2 [cs.DS] UPDATED)

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. …

arxiv dash distributed sequencing