# Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2021.

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

- [Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity](https://mlsanity.com/paper/2405.12252/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε ))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in Oε(n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.