TY - JOUR AU - Kuhnle, Alan PY - 2021/05/18 Y2 - 2024/03/28 TI - Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 35 IS - 9 SE - AAAI Technical Track on Machine Learning II DO - 10.1609/aaai.v35i9.16998 UR - https://ojs.aaai.org/index.php/AAAI/article/view/16998 SP - 8200-8208 AB - We study combinatorial, 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 of the ground set, from 0.039 to nearly 0.193. 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. ER -