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

Abstract

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+\epsilon$, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of $11.657$; and a $(4+O(\epsilon ))$-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of $e+\epsilon$ in $O_{\epsilon }(n\log (n))$ time, close to the best known expected ratio of $e-0.121$ in polynomial time.

arXiv comment30 pages

References in corpus (1)

• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

Cited by in corpus (1)

• Regularized Unconstrained Weakly Submodular Maximization