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

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 - varepsilon. 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 - varepsilon, adaptivity O( log (n) ), and query complexity O( n log (k) ), while the second has approximation ratio 0.193 - varepsilon, adaptivity O( log2 (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.