# Metadata

- Title: Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation
- Authors: Yixin Chen, Wenjing Chen, Alan Kuhnle
- Year: 2025
- Venue: arXiv preprint (`arXiv:2502.07062v2`)
- Primary group: submodular
- Secondary tags: non-monotone, cardinality, parallel, adaptivity, combinatorial, interlaced-greedy
- Problem: parallel / sublinear-adaptivity algorithms for non-monotone submodular maximization under a size constraint, aiming to match the `1 / e` ratio with purely combinatorial methods
- Main guarantee: first combinatorial parallel algorithm matching the `1 / e - epsilon` approximation barrier for size constraints, with `O(log n log k)` adaptivity and `O(n log n log k)` queries up to epsilon factors; also gives a simpler `(1/4 - epsilon)` high-probability algorithm with the same asymptotic efficiency
- Key techniques: simplified interpolated greedy via blended marginal gains, parallel interlace greedy with threshold sampling, and a unified subroutine for both the `(1/4 - epsilon)` and `(1 / e - epsilon)` parallel algorithms
- Status: processed-deep
- Tags: #submodular #non-monotone #parallel #adaptivity #cardinality #combinatorial #1-over-e
- Inbox source: inbox/2502.07062v2.pdf