Parallel algorithm for non-monotone DR-submodular maximization
Files
Published version
Date
2020-08-14
DOI
Authors
Ene, Alina
Nguyen, Huy Le
Version
Published version
OA Version
Citation
Alina Ene, Huy Le Nguyen. 2020. "Parallel Algorithm for Non-Monotone DR-Submodular Maximization." International Conference on Machine Learning
Abstract
In this work, we give a new parallel algorithm
for the problem of maximizing a non-monotone
diminishing returns submodular function subject
to a cardinality constraint. For any desired accuracy
𝜖, our algorithm achieves a 1/e − 𝜖 approximation
using O(log n log(1/𝜖 )/𝜖^3) parallel
rounds of function evaluations. The approximation
guarantee nearly matches the best approximation
guarantee known for the problem in the sequential
setting and the number of parallel rounds
is nearly-optimal for any constant 𝜖. Previous algorithms
achieve worse approximation guarantees
using Ω
(log^2 n) parallel rounds. Our experimental
evaluation suggests that our algorithm obtains
solutions whose objective value nearly matches
the value obtained by the state of the art sequential
algorithms, and it outperforms previous parallel
algorithms in number of parallel rounds, iterations,
and solution quality.
Description
License
Copyright 2020 by the author(s).