# Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint

arXiv: https://arxiv.org/abs/2405.13994 · HTML: https://mlsanity.com/paper/2405.13994/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 48 references that are in the map.
- First posted on arXiv 22 May 2024.

## Builds on (most cited first, 24 of 24)

- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification](https://mlsanity.com/paper/1812.00151/) (2018)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Streaming Weak Submodularity: Interpreting Neural Networks on the Fly](https://mlsanity.com/paper/1703.02647/) (2017)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Risk-Aware Submodular Optimization for Multi-Robot Coordination](https://mlsanity.com/paper/2003.10492/) (2020)
- [Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time](https://mlsanity.com/paper/2010.11420/) (2020)
- [Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization](https://mlsanity.com/paper/1410.0773/) (2014)
- [Constrained Submodular Maximization: Beyond 1/e](https://mlsanity.com/paper/1608.03611/) (2016)
- [Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time](https://mlsanity.com/paper/2009.04979/) (2020)
- [On Maximizing Sums of Non-monotone Submodular and Linear Functions](https://mlsanity.com/paper/2205.15874/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization](https://mlsanity.com/paper/2405.05202/) (2024)
- [Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization](https://mlsanity.com/paper/1802.06212/) (2018)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)

## Built on by (most cited first, 3 of 3)

- [Supportive Token Revealing for Fast Diffusion Language Model Decoding](https://mlsanity.com/paper/2606.04236/) (2026)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Fine-Tuning Diffusion Language Models with Context Selection and Target Weighting](https://mlsanity.com/paper/2609.38385/) (2026)

## Abstract (arXiv)

Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications. However, existing algorithms often struggle with a trade-off between approximation guarantees and practical efficiency. The current state-of-the-art is a recent 0.401-approximation algorithm, but its computational complexity makes it highly impractical. The best practical algorithms for the problem only guarantee 1/e-approximation. In this work, we present a novel algorithm for submodular maximization subject to a cardinality constraint that combines a guarantee of 0.385-approximation with a low and practical query complexity of O(n+k2). Furthermore, we evaluate the empirical performance of our algorithm in experiments based on various machine learning applications, including Movie Recommendation, Image Summarization, and more. These experiments demonstrate the efficacy of our approach.