# Metadata

- Title: Optimal Submodular Maximization in Parallel
- Authors: Yixin Chen, Tonmoy Dey, Alan Kuhnle
- Year: 2021
- Venue: arXiv preprint (`arXiv:2111.07917v3`, November 15, 2021)
- Primary group: submodular
- Secondary tags: monotone, cardinality, parallel, adaptivity, linear-query, thresholding, practical
- Problem: monotone submodular maximization under a cardinality constraint in the adaptive-complexity / parallel-query model
- Main guarantee: gives `LS+PGB`, a nearly optimal parallel algorithm with approximation `1 - 1 / e - eps`, `O(log n)` adaptivity, and expected `O(n)` queries, built from the reusable subroutines `LINEAR SEQ` and `THRESHOLD SEQ`
- Key techniques: linear-query preprocessing, parallel thresholding, greedy boosting from a constant-factor estimate of `OPT`, random block prefixes, and corrected high-probability analysis
- Status: processed-deep, venue-year-to-verify
- Tags: #submodular #monotone #cardinality #parallel #adaptivity #linear-query #thresholding #arXiv
- Inbox source: inbox/2111.07917v3.pdf