cs.DS cs.LG
Nearly Linear Time, Parallelizable Algorithms for Non Monotone Submodular Maximization. We study parallelizable algorithms for maximization of a submodular function, not necessarily monotone, with respect to a cardinality constraint k . We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and query complexity, up to logarithmic factors in the size n of the ground set, from 0.039 epsilon to 0.193 epsilon . We provide two 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) . Heuristic versions of 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.