GreedyML: A Parallel Algorithm for Maximizing Submodular Functions

arXiv:2403.10332v1 Announce Type: cross
Abstract: 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 applications in areas 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 …

abstract algorithm applications approximation arxiv constraints cs.dc cs.ds cs.lg data data sets distributed functions machine machine learning massive memory optimization practical solve summarization type work