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

Code

• gitlab.com/luciacyx/nm-adaptive-code
  OfficialIn papernone★ 0

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 - . 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( (n) ) adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio 1/6 - , adaptivity O( (n) ), and query complexity O( n (k) ), while the second has approximation ratio 0.193 - , adaptivity O( ^2 (n) ), and query complexity O(n (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.

Reproductions