# Metadata

- Title: Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint
- Authors: Murad Tukan, Loay Mualem, Moran Feldman
- Year: 2024
- Venue: arXiv preprint (`arXiv:2405.13994v1`, May 22, 2024); under review at time of preprint
- Primary group: submodular
- Secondary tags: non-monotone, cardinality, practical, local-search, stochastic-greedy, beyond-1-over-e
- Problem: practical non-monotone submodular maximization under a cardinality constraint
- Main guarantee: gives a practical `0.385`-approximation algorithm with only `O(n + k^2)` queries, combining a fast local-search routine with an accelerated stochastic-greedy improvement step
- Key techniques: repeated Sample Greedy for initialization, `FAST-LOCAL-SEARCH` with `O(n + k^2)` complexity, a guided stochastic greedy step based on the local optimum, and returning the better of the local-search and greedy-improvement outputs
- Status: processed-deep
- Tags: #submodular #non-monotone #cardinality #practical #local-search #stochastic-greedy
- Inbox source: inbox/2405.13994v1.pdf