# Metadata

- Title: Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization
- Authors: Yixin Chen, Ankur Nath, Chunli Peng, Alan Kuhnle
- Year: 2024
- Venue: arXiv preprint (`arXiv:2405.05202v3`)
- Primary group: submodular
- Secondary tags: non-monotone, cardinality, matroid, combinatorial, deterministic, local-search, beyond-1-over-e
- Problem: non-monotone submodular maximization under size and general matroid constraints, with emphasis on combinatorial algorithms that beat the `1 / e` barrier without multilinear-extension queries
- Main guarantee: first combinatorial algorithms beyond `1 / e`, achieving `0.385 - epsilon` for size constraints and `0.305 - epsilon` for matroid constraints in `O(kn / epsilon)` queries; also gives deterministic versions with the same ratios and a nearly-linear deterministic `0.377` algorithm
- Key techniques: fast local search to produce a guidance set, guided random greedy and guided interpolated greedy, blended marginal gains analysis, and extracting guidance from unguided interpolated-greedy runs
- Status: processed-deep
- Tags: #submodular #non-monotone #cardinality #matroid #combinatorial #deterministic #beyond-1-over-e
- Inbox source: inbox/2405.05202v3.pdf