# Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 47 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [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)
- [Online Submodular Maximization with Preemption](https://mlsanity.com/paper/1501.05801/) (2015)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Parallel Algorithm for Non-Monotone DR-Submodular Maximization](https://mlsanity.com/paper/1905.13272/) (2019)
- [Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time](https://mlsanity.com/paper/2010.11420/) (2020)
- [Submodular Cost Submodular Cover with an Approximate Oracle](https://mlsanity.com/paper/1908.00653/) (2019)
- [Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time](https://mlsanity.com/paper/2009.04979/) (2020)
- [Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice](https://mlsanity.com/paper/1805.06990/) (2018)
- [Maximizing Monotone Submodular Functions over the Integer Lattice](https://mlsanity.com/paper/1503.01218/) (2015)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Improved Deterministic Algorithms for Non-monotone Submodular Maximization](https://mlsanity.com/paper/2208.14388/) (2022)
- [A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns](https://mlsanity.com/paper/1606.08362/) (2016)
- [An Efficient Streaming Algorithm for the Submodular Cover Problem](https://mlsanity.com/paper/1611.08574/) (2016)
- [SAGA: A Submodular Greedy Algorithm For Group Recommendation](https://mlsanity.com/paper/1712.09123/) (2017)
- [Scalable Bicriteria Algorithms for the Threshold Activation Problem in Online Social Networks](https://mlsanity.com/paper/1701.08799/) (2017)
- [Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time](https://mlsanity.com/paper/2104.06873/) (2021)
- [Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice](https://mlsanity.com/paper/2111.10175/) (2021)

## Abstract (arXiv)

This work studies the non-monotone DR-submodular Maximization over a ground set of n subject to a size constraint k. We propose two approximation algorithms for solving this problem named FastDrSub and FastDrSub++. FastDrSub offers an approximation ratio of 0.044 with query complexity of O(n log(k)). The second one, FastDrSub++, improves upon it with a ratio of 1/4-ε within query complexity of (n log k) for an input parameter ε >0. Therefore, our proposed algorithms are the first constant-ratio approximation algorithms for the problem with the low complexity of O(n log(k)). Additionally, both algorithms are experimentally evaluated and compared against existing state-of-the-art methods, demonstrating their effectiveness in solving the Revenue Maximization problem with DR-submodular objective function. The experimental results show that our proposed algorithms significantly outperform existing approaches in terms of both query complexity and solution quality.