# Metadata

- Title: Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
- Authors: Yixin Chen, Alan Kuhnle
- Year: 2020
- Venue: arXiv preprint (`arXiv:2009.01947v5`, September 3, 2020)
- Primary group: submodular
- Secondary tags: non-monotone, cardinality, adaptivity, parallel, thresholding, query-efficiency, practical
- Problem: non-monotone submodular maximization under a cardinality / size constraint with low adaptivity and nearly linear query complexity
- Main guarantee: gives `AST` with ratio `1 / 6 - eps` in `O(log n)` adaptivity and `O(n log k)` queries, `ATG` with ratio `0.193 - eps` in `O(log n log k)` adaptivity and `O(n log k)` queries, and a new `ThreshSeq` subroutine that works correctly for non-monotone objectives
- Key techniques: high-probability threshold sampling via two coupled sets, double-threshold framework, adaptive threshold greedy, and decomposition through unconstrained-maximization subproblems
- Status: processed-deep, venue-year-to-verify
- Tags: #submodular #non-monotone #cardinality #parallel #adaptivity #thresholding #approximation #arXiv
- Inbox source: inbox/2009.01947v5.pdf