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

AAAI 2021 pp. 8200-8208

doi:10.1609/AAAI.V35I9.16998 /aaai/2021/kuhnle2021aaai-nearly/

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.

PDF AAAI Semantic Scholar

Cite

Text

Kuhnle. "Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I9.16998

Markdown

[Kuhnle. "Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/kuhnle2021aaai-nearly/) doi:10.1609/AAAI.V35I9.16998

BibTeX

@inproceedings{kuhnle2021aaai-nearly,
  title     = {{Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization}},
  author    = {Kuhnle, Alan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {8200-8208},
  doi       = {10.1609/AAAI.V35I9.16998},
  url       = {https://mlanthology.org/aaai/2021/kuhnle2021aaai-nearly/}
}