# Metadata

- Title: The Fast Algorithm for Submodular Maximization
- Authors: Adam Breuer, Eric Balkanski, Yaron Singer
- Year: 2019
- Venue: arXiv preprint (`arXiv:1907.06173v1`, July 14, 2019)
- Primary group: submodular
- Secondary tags: monotone, cardinality, parallel, low-adaptivity, adaptive-sequencing, practical
- Problem: practical parallel maximization of monotone submodular functions under a cardinality constraint
- Main guarantee: proposes FAST (Fast Adaptive Sequencing Technique), achieving `1 - 1 / e - eps` with `O(log n * log^2 log k)` adaptivity and `O(n log log k)` queries, while emphasizing small constants and strong empirical runtime
- Key techniques: adaptive sequencing instead of adaptive sampling, binary search over OPT guesses and sequence prefixes, preprocessing of high-value sequence elements, lazy updates, and high-probability robustness for parallel search
- Status: processed-deep, venue-year-to-verify
- Tags: #submodular #monotone #cardinality #parallel #low-adaptivity #adaptive-sequencing #practical #arXiv
- Inbox source: inbox/1907.06173v1.pdf