Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization

Authors

  • Alan Kuhnle Florida State University, Tallahassee, Florida

Keywords:

Optimization, Other Foundations of Search & Optimization

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Kuhnle, A. (2021). Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 8200-8208. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16998

Issue

Section

AAAI Technical Track on Machine Learning II