# GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions

arXiv: https://arxiv.org/abs/2403.10332 · HTML: https://mlsanity.com/paper/2403.10332/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 15 Mar 2024.

## Builds on (most cited first, 10 of 10)

- [AGATHA: Automatic Graph-mining And Transformer based Hypothesis generation Approach](https://mlsanity.com/paper/2002.05635/) (2020)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [MOLIERE: Automatic Biomedical Hypothesis Generation System](https://mlsanity.com/paper/1702.06176/) (2017)
- [Submodularity in Action: From Machine Learning to Signal Processing Applications](https://mlsanity.com/paper/2006.09905/) (2020)
- [Streaming Weak Submodularity: Interpreting Neural Networks on the Fly](https://mlsanity.com/paper/1703.02647/) (2017)
- [Optimal Algorithms for Submodular Maximization with Distributed Constraints](https://mlsanity.com/paper/1909.13676/) (2019)
- [Submodular Function Maximization in Parallel via the Multilinear Relaxation](https://mlsanity.com/paper/1807.08678/) (2018)
- [Near-Optimal Sparse Sensing for Gaussian Detection with Correlated Observations](https://mlsanity.com/paper/1710.09676/) (2017)
- [A Parallel Approximation Algorithm for Maximizing Submodular b-Matching](https://mlsanity.com/paper/2107.05793/) (2021)

## Abstract (arXiv)

We describe a parallel approximation algorithm for maximizing monotone submodular functions subject to hereditary constraints on distributed memory multiprocessors. Our work is motivated by the need to solve submodular optimization problems on massive data sets, for practical contexts such as data summarization, machine learning, and graph sparsification. Our work builds on the randomized distributed RandGreedi algorithm, proposed by Barbosa, Ene, Nguyen, and Ward (2015). This algorithm computes a distributed solution by randomly partitioning the data among all the processors and then employing a single accumulation step in which all processors send their partial solutions to one processor. However, for large problems, the accumulation step exceeds the memory available on a processor, and the processor that performs the accumulation becomes a computational bottleneck. Hence we propose a generalization of the RandGreedi algorithm that employs multiple accumulation steps to reduce the memory required. We analyze the approximation ratio and the time complexity of the algorithm (in the BSP model). We evaluate the new GreedyML algorithm on three classes of problems, and report results from large-scale data sets with millions of elements. The results show that the GreedyML algorithm can solve problems where the sequential Greedy and distributed RandGreedi algorithms fail due to memory constraints. For certain computationally intensive problems, the GreedyML algorithm is faster than the RandGreedi algorithm. The observed approximation quality of the solutions computed by the GreedyML algorithm closely matches those obtained by the RandGreedi algorithm on these problems.