Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
We present combinatorial and parallelizable algorithms for the 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 1/6 − ε, and even further to 0.193 …