Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint

Abstract

We present combinatorial and parallelizable algorithms for maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to $0.193-\epsilon$. The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in $O(\log (n))$ adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio $1/6-\epsilon$, adaptivity $O(\log (n))$, and query complexity $O(n\log (k))$, while the second has approximation ratio $0.193-\epsilon$, adaptivity $O({\log }^2(n))$, and query complexity $O(n\log (k))$. Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.

arXiv comment39 pages

References in corpus (7)

• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
• Non-monotone Submodular Maximization in Exponentially Fewer Iterations
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
• Parallel Algorithm for Non-Monotone DR-Submodular Maximization
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
• Unconstrained Submodular Maximization with Constant Adaptive Complexity

Cited by in corpus (1)

• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models