GreedyML: A Parallel Algorithm for Maximizing Submodular Functions
Shivaram Gopal S M Ferdous Hemanta K. Maji Alex Pothen
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 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
could exceed the memory available on a processor, and the processor which
performs the accumulation could become a computational bottleneck.
  Here, 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 also evaluate the new GreedyML algorithm on three classes of
problems, and report results from massive 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 can be 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.