Fixed-Parameter Tractable Submodular Maximization over a Matroid

Nematollahi, Shamisa; Vladu, Adrian; Zhao, Junyao

doi:10.4230/LIPIcs.ITCS.2026.105

Fixed-Parameter Tractable Submodular Maximization over a Matroid

Shamisa Nematollahi

CNRS, IRIF, Université Paris Cité, Paris, France Adrian Vladu

CNRS, IRIF, Université Paris Cité, Paris, France Junyao Zhao

CNRS, IRIF, Université Paris Cité, Paris, France

Abstract

In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank $r$ is treated as a fixed parameter that is independent of the total number of elements $n$ . We provide two FPT algorithms: one for the offline setting and another for the random-order streaming setting. Our streaming algorithm achieves a $\nicefrac{{1}}{{2}}-\varepsilon$ approximation using $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ memory, while our offline algorithm obtains a $1-\nicefrac{{1}}{{e}}-\varepsilon$ approximation with $n\cdot 2^{\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(% \varepsilon)}\right)}$ runtime and $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ memory. Both approximation factors are near-optimal in their respective settings, given existing hardness results. In particular, our offline algorithm demonstrates that – unlike in the polynomial-time regime – there is essentially no separation between monotone and non-monotone submodular maximization under a matroid constraint in the FPT framework.

Keywords and phrases:

Submodular maximization, matroids, parameterized complexity, streaming algorithms

Funding:

Shamisa Nematollahi: Partially supported by the French Agence Nationale de la Recherche (ANR) under grant ANR-21-CE48-0016 (project COMCOPT).

Adrian Vladu: Partially supported by the French Agence Nationale de la Recherche (ANR) under grant ANR-21-CE48-0016 (project COMCOPT).

Junyao Zhao: Supported by a postdoctoral fellowship from the Fondation Sciences Mathématiques de Paris (FSMP).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Submodular maximization under a matroid constraint is a fundamental problem in combinatorial optimization, where we are given¹¹1We assume that the submodular function $f$ is given by a value oracle that outputs $f(X)$ for input $X\subseteq[n]$ , and the matroid ${\mathcal{M}}$ is given by a membership oracle that answers whether $X\in{\mathcal{M}}$ for input $X\subseteq[n]$ . a submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ and a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ with rank $r\in{\mathbb{N}}^{+}$ , and our task is to find a set of elements $X\in{\mathcal{M}}$ that maximizes the function value $f(X)$ . For this problem, there is a well-known gap between monotone (i.e., non-decreasing) and non-monotone submodular functions: For monotone submodular functions, the optimal polynomial-time algorithm achieves a $1-\nicefrac{{1}}{{e}}$ approximation to the optimal solution [8], whereas for non-monotone submodular functions, no polynomial-time algorithm can obtain a $0.478$ approximation [17, 12], even for the special case of the cardinality constraint [25], where the matroid ${\mathcal{M}}$ simply consists of all subsets of $[n]$ with size at most $r$ .

One of the most important paradigms in theoretical computer science for overcoming the limitations of polynomial-time algorithms is parameterized complexity, which treats a specific component of the problem as a parameter that is fixed at a small value. In the context of matroid-constrained submodular maximization, it is natural to assume that the matroid rank $r$ is a small parameter²²2For example, in data summarization [23], given a large image dataset, an algorithm needs to choose a representative subset of images that is small enough to fit the screen of our smartphones. and design fixed-parameter tractable (FPT) algorithms, i.e., algorithms with runtime $h(r)\cdot\textnormal{poly}(n)$ , where $h$ can be any finite function.

For the special case of the cardinality constraint, [26] designed an FPT algorithm that guarantees a $0.539$ approximation for non-monotone submodular functions, showing a substantial advantage of FPT algorithms over polynomial-time algorithms. On the hardness side, essentially the only known query complexity lower bound that applies to FPT algorithms is from the classic work of [24]. They proved that any algorithm that achieves a better-than- $(1-\nicefrac{{1}}{{e}})$ approximation requires $n^{\Omega(r)}$ queries to the value oracle, a result that holds for both monotone and non-monotone submodular maximization with the cardinality constraint. These results seem to suggest that the gap between monotone and non-monotone submodular maximization (at least for the cardinality constraint) could be narrowed further, or perhaps even closed, in the FPT regime. This brings us to the question:

For matroid/cardinality-constrained non-monotone submodular maximization, what is the best possible approximation ratio that can be achieved by FPT algorithms³³3The special case of this question for the cardinality constraint was posed by [26].? Is there a separation between monotone and non-monotone submodular maximization under a matroid/cardinality constraint in the FPT framework?

In this paper, we reveal a surprising answer to this question: There is essentially no separation between monotone and non-monotone submodular maximization under a matroid constraint in the FPT regime. Specifically, we design a nearly $(1-\nicefrac{{1}}{{e}})$ -approximation FPT algorithm (Algorithm 3) for general (non-monotone) submodular maximization subject to a matroid constraint.

Theorem 1 (Restatement of Theorem 28).

There is an FPT algorithm that achieves a $1-\nicefrac{{1}}{{e}}-\varepsilon$ approximation for maximizing any non-negative submodular function under a matroid constraint, with $n\cdot 2^{\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(% \varepsilon)}\right)}$ runtime and $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ memory for any $\varepsilon>0$ .

The bedrock of our $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation FPT algorithm is a subroutine (Subroutine 2) that can be simplified into a random-order semi-streaming algorithm (Algorithm 1), and it has significant implications for the streaming setting as well. Briefly, a random-order streaming algorithm makes a single pass over elements of $[n]$ in a uniformly random order. During the pass, the algorithm maintains a subset of visited elements in a memory buffer of bounded size, and it is allowed to make unlimited queries to the value oracle of the function $f$ and the membership oracle of the matroid ${\mathcal{M}}$ for any subset of elements stored in its memory. In the literature, there is particular interest in streaming algorithms that use $\widetilde{{\mathcal{O}}}(r)$ memory, which are known as semi-streaming algorithms.

Our random-order semi-streaming algorithm (Algorithm 1) achieves a nearly $\nicefrac{{1}}{{2}}$ approximation. (We note that a nearly $\nicefrac{{1}}{{2}}$ approximation is known to be achievable by a streaming algorithm with $2^{{\mathcal{O}}(r)}$ memory, for the more general setting of matroid intersection constraints and adversarial-order streams [15].) This matches the lower bound established by [26], which asserts that any random-order streaming algorithm exceeding $\nicefrac{{1}}{{2}}$ approximation must use $\Omega\left(\frac{n}{r^{2}}\right)$ memory, even for the special case of the cardinality constraint.

Theorem 2 (Restatement of Theorem 16).

There is a random-order semi-streaming algorithm that achieves a $\nicefrac{{1}}{{2}}-\varepsilon$ approximation for maximizing any non-negative submodular function under a matroid constraint, using $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ memory for any $\varepsilon>0$ .

In comparison, the previous best random-order semi-streaming algorithm for maximizing monotone submodular functions under a matroid constraint achieves a $\left(\frac{1-e^{-2}}{2}\approx 0.432\right)$ approximation [27]. For non-monotone functions, the best known semi-streaming algorithm obtains a $0.1921$ approximation [14], though this algorithm applies to the more restrictive adversarial-order streaming setting. We highlight that the algorithms of [27] and [14] run in polynomial time, whereas our algorithm runs in FPT time.

1.1 Overview of our approach

Deferring a more detailed exposition to the main sections, we provide an overview of our algorithms and techniques. As mentioned previously, the core of our $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation algorithm (Algorithm 3) is Subroutine 2, which can be simplified into a $(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation semi-streaming algorithm (Algorithm 1). We call this subroutine continuous greedy filtering. It is inspired by a filtering technique developed by [26] for cardinality-constrained non-monotone submodular maximization, and a fast continuous greedy algorithm designed by [4] for matroid-constrained monotone submodular maximization.

Continuous greedy filtering

The initial phase of this subroutine maintains a fractional solution over $\frac{1}{\varepsilon}$ epochs. In each epoch $t\in\left[\frac{1}{\varepsilon}\right]$ , the subroutine constructs an incremental sequence of integral solutions $S^{t}_{1},\dots,S^{t}_{r}\in{\mathcal{M}}$ through $r$ selection steps. At each step $i\in[r]$ , it samples a small subset of elements. Among the elements that can be added to $S^{t}_{i-1}$ , it selects the element $s_{i}^{t}$ that maximizes the marginal value relative to the current fractional solution $x^{t}_{i-1}$ (a “weighted average” of the integral solutions $S^{1}_{r},\dots,S^{t-1}_{r},S^{t}_{i-1}$ ). The integral solution $S^{t}_{i}$ is then updated to be $S^{t}_{i-1}\cup\{s_{i}^{t}\}$ .

In the second phase, the subroutine uses the integral solutions constructed in the first phase as a filter to select a subset $H$ of elements from $[n]$ . Specifically, for each element $e\in[n]$ , $e$ is included in $H$ if it can be added to $S_{i-1}^{t}$ and its marginal value with respect to $x^{t}_{i-1}$ exceeds that of element $s_{i}^{t}$ , for some $t\in\left[\frac{1}{\varepsilon}\right]$ and $i\in[r]$ . A minor detail is that the subroutine rounds the marginal values of $e$ and $s_{i}^{t}$ to the closest power of $1+\varepsilon$ before comparing them. This detail will keep the subroutine’s memory usage nearly linear in the matroid rank $r$ .

This subroutine achieves a key property: We partition the optimal solution $O$ into two sets $O_{L}:=O\setminus H$ and $O_{H}:=O\cap H$ . Then, the subroutine guarantees that there is a feasible subset of $\bigcup_{t=1}^{1/\varepsilon}S_{r}^{t}$ that is a $1-\nicefrac{{1}}{{e}}-\varepsilon$ approximation to the partial optimal solution $O_{L}$ .

$(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation: a recursive approach

Our $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation algorithm applies the continuous greedy filtering subroutine recursively on refined instances. Specifically, after the first invocation of the subroutine on the input instance $(f,{\mathcal{M}})$ , if the value of $O_{H}$ is negligible, then by submodularity, $O_{L}$ must account for almost all the optimal value. In this case, because of the aforementioned property, our algorithm can find a $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximate solution through an exhaustive search over all subsets of $\bigcup_{t=1}^{1/\varepsilon}S_{r}^{t}$ . If otherwise, our algorithm enumerates all subsets of $H$ to identify $O_{H}$ (the algorithm will encounter $O_{H}$ in some iteration of the enumeration, even though it does not know what $O_{H}$ is), and then, it recursively applies the above process to a refined instance $(f^{\prime},{\mathcal{M}}^{\prime})$ , where the matroid ${\mathcal{M}}^{\prime}$ is obtained by contracting the original matroid ${\mathcal{M}}$ by the set $O_{H}$ (see Definition 9), and the function $f^{\prime}$ is defined by $f^{\prime}(X):=f(X\cup O_{H})$ . The high-level intuition is that, after sufficiently many recursions, we will eventually reach the first case, where the value of $O_{H}^{\prime}$ (the analogue of $O_{H}$ in the refined instance) is negligible.

$(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation semi-streaming algorithm: single-epoch filtering

Our random-order semi-streaming algorithm simplifies continuous greedy filtering by performing a single-epoch greedy procedure to construct an integral solution in the first $\varepsilon$ fraction of the random stream, followed by a similar filtering phase in the remaining stream. The final solution is obtained by enumerating all subsets of elements selected during these two phases and choosing the best one. In the main body of the paper, we will first present this simpler algorithm and its analysis.

Comparison to [26]

Briefly, [26] first designed a $(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation random-order streaming algorithm with quadratic memory for cardinality-constrained non-monotone submodular maximization, based on the filtering technique. They then identified cases where their streaming algorithm only achieves a $\nicefrac{{1}}{{2}}$ approximation, and introduced an offline postprocessing procedure to handle those cases and improve the approximation ratio. Their analysis of this procedure relies on a factor-revealing program to balance different cases. To better leverage this factor-revealing program, they extended their postprocessing procedure to a recursive one, which led to a $0.539$ -approximation FPT algorithm.

Our semi-streaming algorithm is a generalization of their streaming algorithm to the matroid constraint, with improved memory usage. Compared to their $0.539$ -approximation FPT algorithm, the two main novelties of our $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation algorithm, as highlighted above, are (i) the combination of the filtering technique and the continuous greedy algorithm, which enables our subroutine to achieve the aforementioned key property under the matroid constraint, and (ii) a natural recursive procedure that applies the subroutine repeatedly to refine the problem instance. This differs significantly from the recursive procedure of [26], which is used only to postprocess an output produced once by their streaming algorithm.

1.2 Additional related work

FPT submodular maximization

The parameterized complexity of submodular maximization was first studied by [28], who provided FPT approximation schemes for maximizing $p$ -separable monotone submodular functions under the cardinality constraint, assuming that both the cardinality constraint and $p$ are fixed parameters. If the cardinality constraint is the only parameter, without further assumptions, even FPT algorithms cannot obtain a better-than- $(1-\nicefrac{{1}}{{e}})$ approximation for monotone submodular functions, both in terms of query complexity [24] and computational complexity under the Gap-Exponential Time Hypothesis [11, 22]. For non-monotone submodular maximization under the cardinality constraint, [26] gave a $0.539$ -approximation FPT algorithm, while the current best polynomial-time algorithm achieves a $0.401$ approximation [6], which also applies to the matroid constraint.

Streaming submodular maximization

In the random-order streaming setting, [1] designed a nearly $(1-\nicefrac{{1}}{{e}})$ -approximation semi-streaming algorithm for monotone submodular maximization subject to a cardinality constraint, which was later simplified by [21] to reduce the memory size. Moreover, under the cardinality constraint, [26] designed a quadratic-memory streaming algorithm that achieves a $0.5029$ approximation and a $\nicefrac{{1}}{{2}}$ approximation for symmetric and asymmetric submodular maximization respectively. Under the matroid constraint, [27] gave a $\frac{1-e^{-2}}{2}$ -approximation semi-streaming algorithm for monotone submodular maximization. All these random-order streaming algorithms (and ours) also apply to the (similar but incomparable) secretary with shortlists model [1].

In the adversarial-order streaming setting, [3] designed a nearly $\nicefrac{{1}}{{2}}$ -approximation semi-streaming algorithm for cardinality-constrained monotone submodular maximization, which was later improved by [20] to achieve a linear memory size. On the hardness side, [19] showed that any streaming algorithm for monotone submodular maximization that achieves an approximation better than $\tfrac{2}{2+\sqrt{2}}$ under a cardinality constraint must use $\Omega\big(\tfrac{n}{r^{2}}\big)$ memory, while attaining an approximation better than $\tfrac{r}{2r-1}$ under a partition matroid constraint requires $\Omega\big(\tfrac{n}{r}\big)$ memory. Later, [16] proved that any streaming algorithm achieving a better-than- $\nicefrac{{1}}{{2}}$ approximation for cardinality-constrained monotone submodular maximization requires $\Omega\big(\tfrac{n}{r^{3}}\big)$ memory. More recently, [2] designed a nearly $\nicefrac{{1}}{{2}}$ -approximation semi-streaming algorithm for cardinality-constrained non-monotone submodular maximization, which is also an FPT algorithm (although not explicitly stated in their paper). Furthermore, matroid-constrained submodular maximization in the adversarial-order streaming setting was first studied by [9], who provided a $\nicefrac{{1}}{{4}}$ -approximation semi-streaming algorithm for monotone functions. This was recently improved to a $0.3178$ approximation by [14], who also gave a $0.1921$ approximation for non-monotone functions. Finally, we mention that [14] developed a multi-pass nearly $(1-\nicefrac{{1}}{{e}})$ -approximation semi-streaming algorithm for matroid-constrained monotone submodular maximization, which also builds on the continuous greedy algorithm of [4]. However, their approach is very different from ours.

2 Preliminaries

2.1 Submodular functions and matroids

We first introduce submodular functions, matroids, and their associated concepts and properties. Given a ground set $[n]$ and a non-negative discrete function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ , for any $X,Y\subseteq[n]$ , we let $f(X|Y)$ denote the marginal value of $X$ with respect to $Y$ , i.e., $f(X|Y):=f(X\cup Y)-f(Y)$ .

Definition 3 (submodular function).

A non-negative function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ is submodular, if it satisfies that $f(X|Y)\geq f(X|Z)$ for any $X\subseteq[n]$ and any $Y\subseteq Z\subseteq[n]$ .

For any vector $x\in[0,1]^{n}$ , we use the notation ${\mathcal{R}}(x)$ to refer to a random set such that each element of $[n]$ appears in ${\mathcal{R}}(x)$ independently with probability $x_{i}$ , and we define the multi-linear extension of a submodular function as follows.

Definition 4 (multi-linear extension).

The multi-linear extension $F:[0,1]^{n}\to{\mathbb{R}}_{\geq 0}$ of a submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ is given by

F(x):=\mathbb{E}[f({\mathcal{R}}(x))]=\sum_{S\subseteq[n]}\prod_{i\in S}x_{i}% \cdot\prod_{i\in[n]\setminus S}(1-x_{i})\cdot f(S)\textrm{ for all }x\in[0,1]^% {n}.

Moreover, for any $x,y\in[0,1]^{n}$ such that $x+y\in[0,1]^{n}$ , we let $F(x|y)$ denote the marginal value of $x$ with respect to $y$ , i.e., $F(x|y):=F(x+y)-F(y)$ .

We are interested in the problem of maximizing a non-negative submodular function subject to a matroid constraint. A matroid is a set system that satisfies certain independence structure.

Definition 5 (matroid).

A set system ${\mathcal{M}}\subseteq 2^{[n]}$ is a matroid⁴⁴4In the literature, a matroid is often represented as a pair $([n],{\mathcal{M}})$ , where $[n]$ is the ground set and ${\mathcal{M}}\subseteq 2^{[n]}$ is the family of independent sets. For simplicity, we refer to the matroid simply as ${\mathcal{M}}$ throughout this paper. if the following conditions hold:

i.

$\emptyset\in{\mathcal{M}}$ .
ii.

If $X\in{\mathcal{M}}$ , then $Y\in{\mathcal{M}}$ for all $Y\subseteq X$ .
iii.

If $X,Y\in{\mathcal{M}}$ and $|Y|<|X|$ , then there exists $i\in X\setminus Y$ such that $Y\cup\{i\}\in{\mathcal{M}}$ .

Given a matroid, we define its rank, bases, restriction and contraction as follows.

Definition 6 (rank).

Given a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ , the rank of ${\mathcal{M}}$ is $r_{{\mathcal{M}}}:=\max_{X\in{\mathcal{M}}}|X|$ .

Definition 7 (base).

Given a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ , we say that a set $B\in{\mathcal{M}}$ is a base of ${\mathcal{M}}$ , if $B\cup\{i\}\notin{\mathcal{M}}$ for all $i\in[n]$ .

Definition 8 (restriction).

Given a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ and a set $S\subseteq[n]$ , we define the restriction of ${\mathcal{M}}$ to $S$ as ${\mathcal{M}}_{S}:=\{X\subseteq S\mid X\in{\mathcal{M}}\}$ . It is well-known that the restriction ${\mathcal{M}}_{S}$ is a matroid.

Definition 9 (contraction).

Given a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ and a set $S\subseteq[n]$ , we let ${\mathcal{M}}/S$ denote the contraction of ${\mathcal{M}}$ by $S$ , which is given by ${\mathcal{M}}/S:=\{X\subseteq[n]\setminus S\mid X\cup S^{\prime}\in{\mathcal{M% }}\textrm{ for all }S^{\prime}\subseteq S\textrm{ such that }S^{\prime}\in{% \mathcal{M}}\}$ . It is well-known that the contraction ${\mathcal{M}}/S$ is a matroid, and its membership oracle can be efficiently evaluated using the membership oracle of ${\mathcal{M}}$ .

In matroid-constrained submodular maximization, an algorithm ALG is given a non-negative submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ and a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ , and its task is to find a feasible set $X\in{\mathcal{M}}$ that maximizes $f(X)$ . Throughout the paper, we denote the optimal solution by $O$ , i.e., $O:=\operatorname*{arg\,max}_{X\in{\mathcal{M}}}f(X)$ (and we reserve ${\mathcal{O}}$ for the Big-O notation to avoid confusion). We say that ALG achieves an $\alpha$ approximation with $\alpha\in[0,1]$ , if its solution set $X_{\textnormal{ALG}}$ satisfies that $\mathbb{E}[f(X_{\textnormal{ALG}})]\geq\alpha\cdot f(O)$ , where the expectation is taken over the randomness of ALG (and the arrival order of the elements, in case ALG is a random-order streaming algorithm, which we will introduce shortly). Moreover, we assume that the matroid rank $r_{{\mathcal{M}}}$ is a fixed parameter that does not depend on the total number of elements $n$ (and hence, $r_{{\mathcal{M}}}=o(n)$ ⁵⁵5If $r_{{\mathcal{M}}}=\Omega(n)$ , then an FPT algorithm with $2^{{\mathcal{O}}(r_{{\mathcal{M}}})}$ runtime can simply enumerate all subsets of $[n]$ , and a streaming algorithm with ${\mathcal{O}}(r_{{\mathcal{M}}})$ memory can simply store all elements of $[n]$ , rendering the problem trivial.), and we are interested in fixed-parameter tractable (FPT) algorithms, i.e., algorithms with runtime $h(r_{{\mathcal{M}}})\cdot\textnormal{poly}(n)$ , where $h$ can be any finite function.

2.2 Random-order streaming model

Besides the standard offline setting (where all elements in the ground set $[n]$ are presented to the algorithm from the outset), we are also interested in the random-order streaming setting, where elements in $[n]$ arrive in a uniformly random order as a data stream.

In this setting, an algorithm has a memory buffer of a limited size (which is $\widetilde{{\mathcal{O}}}(r_{{\mathcal{M}}})$ for semi-streaming algorithms). Each time when a new element arrives, the algorithm decides how to update its memory buffer, i.e., whether to store the new element, remove some previously stored elements, or modify other stored information. At any point, the algorithm can make any number of queries to the value oracle of the submodular function and the membership oracle of the matroid, provided that the input for the query is a subset of elements stored in its memory. At the end of the stream, the algorithm outputs a subset of elements from its memory that satisfies the matroid constraint.

2.3 Other useful notions and lemmata

We use the notations $\mathbf{1}_{S}\in\{0,1\}^{n}$ and $\mathbf{1}_{e}\in\{0,1\}^{n}$ to represent the indicator vectors for any set $S\subseteq[n]$ and for any element $e\in[n]$ respectively, and let $\mathbf{0}$ denote the all-zero vector. Moreover, we define a rounding operator that will be the key to reducing the memory usage of our algorithms.

Definition 10 (rounding operator).

Given any finite non-empty set of real numbers $I$ , we use the notation $\left\lfloor\cdot\right\rfloor_{I}$ to denote the rounding operator that maps any real number $a\in{\mathbb{R}}$ to its greatest lower bound in $I$ , or to the smallest number in $I$ if no lower bound exists, i.e., $\left\lfloor a\right\rfloor_{I}:=\max\{i\in I\mid i\leq a\}$ if $a\geq\min I$ , and $\left\lfloor a\right\rfloor_{I}:=\min I$ otherwise.

Then, we present two base exchange lemmas for matroids and two sampling lemmas for non-negative submodular functions.

Lemma 11 ([18, 29]).

Given two bases $B_{1}$ and $B_{2}$ of a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ , and a partition $B_{1}=X_{1}\mathbin{\mathaccent 0{\cdot}\cup}Y_{1}$ , there exists a partition $B_{2}=X_{2}\mathbin{\mathaccent 0{\cdot}\cup}Y_{2}$ such that $X_{1}\mathbin{\mathaccent 0{\cdot}\cup}Y_{2}$ and $X_{2}\mathbin{\mathaccent 0{\cdot}\cup}Y_{1}$ are both bases of ${\mathcal{M}}$ .

Lemma 12 ([5]).

Given two bases $B_{1}$ and $B_{2}$ of a matroid ${\mathcal{M}}\subseteq 2^{[n]}$ , there exists a bijection $h:B_{1}\setminus B_{2}\to B_{2}\setminus B_{1}$ such that for all $e\in B_{1}\setminus B_{2}$ , $(B_{1}\setminus\{e\})\cup\{h(e)\}$ is a base of ${\mathcal{M}}$ .

Lemma 13 ([13, Lemma 2.2]).

Given a non-negative submodular function $f:2^{[n]}\to\mathbb{R}_{\geq 0}$ and a set $X\subseteq[n]$ , if $R$ is a random subset of $X$ such that every element of $X$ appears in $R$ with probability exactly $p$ (not necessarily independently), then we have that $\mathbb{E}[f(R)]\geq(1-p)\cdot f(\emptyset)+p\cdot f(X)$ .

Lemma 14 ([7, Lemma 2.2]).

Given a non-negative submodular function $f:2^{[n]}\to\mathbb{R}_{\geq 0}$ and a set $X\subseteq[n]$ , if $R$ is a random subset of $X$ such that every element of $X$ appears in $R$ with probability at most $p$ (not necessarily independently), then we have that $\mathbb{E}[f(R)]\geq(1-p)\cdot f(\emptyset)$ .

Finally, we state a lemma that follows from standard rounding schemes [8, 10] for matroid-constrained submodular maximization.

Lemma 15.

Given a matroid ${\mathcal{M}}\in 2^{[n]}$ , a submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ , and its multi-linear extension $F:[0,1]^{n}\to{\mathbb{R}}_{\geq 0}$ , for any $x=\sum_{i=1}^{N}\frac{1}{N}\cdot\mathbf{1}_{S_{i}}$ such that $S_{i}\in{\mathcal{M}}$ for all $i\in[N]$ , there exists $X\subseteq\bigcup_{i=1}^{N}S_{i}$ such that $X\in{\mathcal{M}}$ and $f(X)\geq F(x)$ .

3 A $(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation random-order streaming algorithm

In this section, we present our semi-streaming algorithm, Greedy-Filtering (Algorithm 1), which achieves a $\nicefrac{{1}}{{2}}-\varepsilon$ approximation using $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ memory for any submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ and any matroid with rank $r=o(n)$ . Algorithm 1 operates in three phases.

Algorithm 1 Greedy-Filtering

(f,{\mathcal{M}},r,\pi,\varepsilon)

.

Phase 1: Estimating the highest singleton value

Algorithm 1 first identifies the element with the highest singleton value in the initial $\varepsilon$ fraction of the random stream $\pi$ , and sets $w$ to be $\frac{r}{\varepsilon}$ times the value of this element. It treats $w$ as an upper bound on the value of the most valuable element in $[n]$ . If $w$ fails to upper bound this value, we can show that w.h.p., only a few of the most valuable elements contribute non-negligibly to the optimal solution. Hence, to address this, throughout the stream, Algorithm 1 also maintains a set $T$ of the top $\left\lceil\frac{\ln(1/\varepsilon)}{\varepsilon}\right\rceil$ elements with highest singleton values among the elements that have appeared.

Phase 2: Greedily constructing a solution set

Then, Algorithm 1 divides the second $\varepsilon$ fraction of the stream into $r$ windows of equal sizes, and greedily constructs a feasible solution set $S_{r}$ as follows: For each $i\in[r]$ , among all elements in the $i$ -th window $V_{i}$ that can be added to the current solution set $S_{i-1}$ without violating the matroid constraint, Algorithm 1 identifies the element $s_{i}$ with the highest marginal value with respect to $S_{i-1}$ , and updates $S_{i}=S_{i-1}\cup\{s_{i}\}$ . If no element in $V_{i}$ can be added to $S_{i-1}$ without violating the matroid constraint (or all elements in $V_{i}$ that can be added have negative marginal values with respect to $S_{i-1}$ ), the algorithm sets $s_{i}$ to be $s_{1}$ , which acts as a dummy element with zero marginal value with respect to $S_{i-1}$ .

Phase 3: Filtering the remaining stream

Algorithm 1 filters elements in the rest of the stream, keeping only a subset $H$ of them: For each remaining element $e$ , Algorithm 1 adds element $e$ to $H$ if, for some $i\in[r]$ , element $e$ has a strictly higher marginal value with respect to solution set $S_{i-1}$ than element $s_{i}$ . Notably, when comparing the marginal values of $e$ and $s_{i}$ , Algorithm 1 first applies the rounding operator defined in Definition 10 with respect to a set $I$ of geometrically increasing numbers, upper bounded by $w$ . As we will show in the analysis, this coarse comparison of marginal values, based on the rounding operator, is crucial for the algorithm to achieve $\nicefrac{{1}}{{2}}-\varepsilon$ approximation while keeping the memory cost nearly linear in the matroid rank w.h.p. In the algorithm, we also set a hard memory limit at Line 17.

Finally, Algorithm 1 finds the most valuable subset of $T\cup S_{r}\cup H$ that satisfies the matroid constraint through an exhaustive search and returns it as the final solution. The approximation guarantee of Algorithm 1, along with its memory cost, is formally stated in Theorem 16.

Theorem 16.

Given any input submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ , matroid ${\mathcal{M}}\subseteq 2^{[n]}$ with rank $r\in{\mathbb{N}}^{+}$ , and parameter $\varepsilon\in\left(0,\frac{1}{2}\right)$ , Algorithm 1 achieves a $\nicefrac{{1}}{{2}}-\varepsilon^{\prime}$ approximation using ${\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)^{2}}{\varepsilon^{2}}\right)$ memory, where $\varepsilon^{\prime}=8\cdot\sqrt{2\varepsilon+\frac{2r}{n}}$ .

The memory bound follows from a simple calculation: Throughout the data stream, Algorithm 1 only needs to maintain three sets of elements $T,S_{r},H$ (note that it can infer $S_{1},\dots,S_{r-1}$ from $S_{r}$ ). By the construction of $T$ and $S_{r}$ , we have that $|T|=\left\lceil\frac{\ln(1/\varepsilon)}{\varepsilon}\right\rceil={\mathcal{O}% }\left(\frac{1}{\varepsilon^{2}}\right)$ and $|S_{r}|\leq r$ . Moreover, the break condition at Line 17 of Algorithm 1 ensures that $|H|={\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}\right)=% {\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)^{2}}{\varepsilon^{2}}\right)$ , since $|I|=\left\lceil 2\log_{1+\varepsilon}(\frac{r}{\varepsilon})\right\rceil+1={% \mathcal{O}}\left(\frac{\ln(r/\varepsilon)}{\varepsilon}\right)$ . Hence, the total memory cost is ${\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)^{2}}{\varepsilon^{2}}\right)$ .

Next, we prove the approximation guarantee in three main steps: First, we show that unless $\max_{e\in[n]}f(\{e\})\geq\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ (in which case we prove that the most valuable and feasible subset of $T$ is a $1-\varepsilon$ approximation of the optimal solution), w.h.p., the value $w$ in Algorithm 1 is an upper bound on the value of the most valuable element in $[n]$ . Then, we show that not many elements pass the filter in the third phase of Algorithm 1, meaning that w.h.p., the break condition at Line 17 is never met. Finally, in the regular case where $w$ caps the value of the most valuable element and only a few elements pass the filter, we prove that w.h.p., the most valuable and feasible subset of $S_{r}\cup H$ is almost a $\nicefrac{{1}}{{2}}$ approximation of the optimal solution. We implement these three steps in the following three subsections.

3.1 The simple case: $\max_{e\in[n]}f(\{e\})\geq\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$

We first analyze the simple case where $\max_{e\in[n]}f(\{e\})\geq\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ . We note that the set $T$ in Algorithm 1 eventually consists of the top $\left\lceil\frac{\ln(1/\varepsilon)}{\varepsilon}\right\rceil$ elements in $[n]$ with the highest singleton values (and we will only consider this final version of $T$ in the analysis). In Lemma 17, we show that Algorithm 1 achieves a $1-\varepsilon$ approximation in this case.

Lemma 17.

If $\max_{e\in[n]}f(\{e\})\geq\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ , Algorithm 1 obtains a $1-\varepsilon$ approximation.

The proof is provided in the full version.

Given Lemma 17, we can now focus on the cases where $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ . Under this assumption, we show that w.h.p., the value $w$ in Algorithm 1 is an upper bound on $\max_{e\in[n]}f(\{e\})$ . Specifically, we define the set $T^{+}:=\{e^{\prime}\in[n]\mid f(\{e^{\prime}\})\geq\min_{e\in T}f(\{e\})\}$ (note that if there are multiple elements with the same singleton value, $T$ could be a random set because of the random stream, but $T^{+}$ is always deterministic). In Lemma 18, we show that w.h.p., at least one element of $T^{+}$ appears in the first $\varepsilon$ fraction of the random stream $\pi$ , which implies that $w\geq\max_{e\in[n]}f(\{e\})$ , assuming $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ .

Lemma 18.

Let $E_{1}$ denote the event that there exists some element of $T^{+}$ that appears in $V_{0}=\{\pi(1),\dots,\pi(\left\lceil\varepsilon n\right\rceil)\}$ , i.e., the first $\varepsilon$ fraction of the random stream $\pi$ . Then, we have that $\Pr[E_{1}]\geq 1-\varepsilon$ . Moreover, if $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ , then conditioned on event $E_{1}$ , it holds that $w\geq\max_{e\in[n]}f(\{e\})$ .

The proof is provided in the full version.

3.2 The unlikely case: $|H|>\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$

Recall that the set $H$ in Algorithm 1 consists of elements that pass the filter in the third phase (throughout the analysis, we will only consider the final version of $H$ ). In Lemma 19, we show that w.h.p., $|H|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$ , which implies that the break condition at Line 17 of Algorithm 1 is unlikely to be reached.

Lemma 19.

Let $E_{2}$ denote the event that $|H|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$ . Then, $\Pr[E_{2}]\geq 1-\varepsilon$ .

Now we introduce several key concepts that will play important roles in the proof of Lemma 19. First, we notice that in Algorithm 1, each element $s_{i}$ chosen in the second phase acts as a selector in the third phase: for each element $e$ in the third phase of Algorithm 1, the algorithm will include $e$ in set $H$ if it satisfies the selection condition posed by $s_{i}$ , namely, if $S_{i-1}\cup\{e\}\in{\mathcal{M}}$ and $\left\lfloor f(\{e\}|S_{i-1})\right\rfloor_{I}>\left\lfloor f(\{s_{i}\}|S_{i-1% })\right\rfloor_{I}$ (we say that an element $e\in[n]$ is selected by the selector $s_{i}$ if it satisfies this condition). For each $i\in[r]$ , we let $G_{i}$ denote the set of elements selected by $s_{i}$ among all elements appearing after the $i$ -th window in the second phase of Algorithm 1, i.e.,

\textstyle G_{i}:=\{e\in[n]\setminus(\bigcup_{j=0}^{i}V_{j})\mid S_{i-1}\cup\{% e\}\in{\mathcal{M}}\textrm{ and }\left\lfloor f(\{e\}|S_{i-1})\right\rfloor_{I% }>\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\}

(1)

(recall that $V_{0}$ is the set of elements in the first $\varepsilon$ fraction of the stream, and for each $j\in[r]$ , $V_{j}$ is the set of elements in the $j$ -th window during the second phase of Algorithm 1).

We order the selectors according to their indices: $s_{1},\dots,s_{r}$ , and for each $i\in[r]$ , we define

\textstyle H_{i}:=\bigcup_{j=1}^{i}G_{j}\textrm{ (and we let $H_{0}:=\emptyset% $ for completeness)}.

(2)

We say that a selector $s_{i}$ is ineffective if there is an earlier selector $s_{j}$ for some $j<i$ such that $\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\geq\left\lfloor f(\{s_{j}\}% |S_{j-1})\right\rfloor_{I}$ (otherwise we call $s_{i}$ an effective selector). In Claim 20, we show that, as the name suggests, any element that is selected by an ineffective selector $s_{i}$ would have already been selected by an earlier selector $s_{j}$ for some $j<i$ , which implies that $H_{i}=H_{i-1}$ .

Claim 20.

Suppose that $s_{i}$ is an ineffective selector, i.e., there exists some $j<i$ such that $\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\geq\left\lfloor f(\{s_{j}\}% |S_{j-1})\right\rfloor_{I}$ . Then, any element $e\in[n]$ that satisfies the selection condition of $s_{i}$ , i.e., $S_{i-1}\cup\{e\}\in{\mathcal{M}}$ and $\left\lfloor f(\{e\}|S_{i-1})\right\rfloor_{I}>\left\lfloor f(\{s_{i}\}|S_{i-1% })\right\rfloor_{I}$ , also satisfies the selection condition of $s_{j}$ , i.e., $S_{j-1}\cup\{e\}\in{\mathcal{M}}$ and $\left\lfloor f(\{e\}|S_{j-1})\right\rfloor_{I}>\left\lfloor f(\{s_{j}\}|S_{j-1% })\right\rfloor_{I}$ . In particular, this implies that $H_{i}=H_{i-1}$ .

Proof.

We establish the first part of the claim by showing that $S_{i-1}\cup\{e\}\in{\mathcal{M}}$ implies $S_{j-1}\cup\{e\}\in{\mathcal{M}}$ , and $\left\lfloor f(\{e\}|S_{i-1})\right\rfloor_{I}>\left\lfloor f(\{s_{i}\}|S_{i-1% })\right\rfloor_{I}$ implies $\left\lfloor f(\{e\}|S_{j-1})\right\rfloor_{I}>\left\lfloor f(\{s_{j}\}|S_{j-1% })\right\rfloor_{I}$ .

First, since ${\mathcal{M}}$ is a matroid and $S_{j-1}\cup\{e\}\subseteq S_{i-1}\cup\{e\}$ , the condition that $S_{i-1}\cup\{e\}\in{\mathcal{M}}$ implies the condition that $S_{j-1}\cup\{e\}\in{\mathcal{M}}$ .

Moreover, because $f$ is a submodular function and $S_{j-1}\subseteq S_{i-1}$ , it holds that $f(\{e\}|S_{j-1})\geq f(\{e\}|S_{i-1})$ , which implies that $\left\lfloor f(\{e\}|S_{j-1})\right\rfloor_{I}\geq\left\lfloor f(\{e\}|S_{i-1}% )\right\rfloor_{I}$ , by monotonicity of the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ (Definition 10). Hence, the condition that $\left\lfloor f(\{e\}|S_{i-1})\right\rfloor_{I}>\left\lfloor f(\{s_{i}\}|S_{i-1% })\right\rfloor_{I}$ implies that $\left\lfloor f(\{e\}|S_{j-1})\right\rfloor_{I}>\left\lfloor f(\{s_{i}\}|S_{i-1% })\right\rfloor_{I}$ . Since we assume that $\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\geq\left\lfloor f(\{s_{j}\}% |S_{j-1})\right\rfloor_{I}$ , it follows that $\left\lfloor f(\{e\}|S_{j-1})\right\rfloor_{I}>\left\lfloor f(\{s_{j}\}|S_{j-1% })\right\rfloor_{I}$ .

Next, we prove the second part of the claim: $H_{i}=H_{i-1}$ . Recall that every element $e\in G_{i}$ appears after the $i$ -th window and satisfies the selection condition of $s_{i}$ , which implies that element $e$ also appears after the $j$ -th window (because $j<i$ ) and satisfies the selection condition of $s_{j}$ (because of the first part of the claim). It follows that every element $e\in G_{i}$ belongs to $G_{j}$ . Hence, we have that $G_{i}\subseteq G_{j}\subseteq H_{i-1}$ , since $H_{i-1}=\bigcup_{\ell=1}^{i-1}G_{\ell}$ and $j\leq i-1$ . Finally, $H_{i}=H_{i-1}$ follows from $H_{i}=G_{i}\cup H_{i-1}$ and $G_{i}\subseteq H_{i-1}$ . $\hfill\vartriangleleft$

Now observe that the set $H$ in Algorithm 1 is a subset of $H_{r}$ . Hence, to upper bound $|H|$ , it suffices to upper bound $|H_{r}|$ . If we could prove that for each $i\in[r]$ , $|H_{i}\setminus H_{i-1}|={\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)}{% \varepsilon}\right)$ holds w.h.p., conditioned on $s_{i}$ being an effective selector, then Lemma 19 would follow immediately. Indeed, Claim 20 states that $H_{i}\setminus H_{i-1}=\emptyset$ for every ineffective selector $s_{i}$ , and thus, we have that $H_{r}=\bigcup_{i\in[r]\textrm{ s.t.}\,s_{i}\textrm{ is an effective selector}}% (H_{i}\setminus H_{i-1})$ . Notice that there can be at most $|I|$ effective selectors because of the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ (specifically, any two distinct effective selectors $s_{i}$ and $s_{j}$ must satisfy that $\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\neq\left\lfloor f(\{s_{j}\}% |S_{j-1})\right\rfloor_{I}$ , and there are only $|I|$ distinct values in the range of $\left\lfloor\cdot\right\rfloor_{I}$ ). Therefore, if $|H_{i}\setminus H_{i-1}|={\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)}{% \varepsilon}\right)$ holds for every effective selector $s_{i}$ , then it would follow that $|H_{r}|={\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}\right)$ .

However, there is a caveat to the above argument: $|H_{i}\setminus H_{i-1}|={\mathcal{O}}\left(\frac{r\ln(r/\varepsilon)}{% \varepsilon}\right)$ does not always hold w.h.p., conditioned on $s_{i}$ being an effective selector. It is possible to construct instances where $|H_{i}\setminus H_{i-1}|=\mathcal{\omega}\left(\frac{r\ln(r/\varepsilon)}{% \varepsilon}\right)$ always holds, conditioned on $s_{i}$ being an effective selector. Fortunately, if this is the case, we can show that the probability that $s_{i}$ is an effective selector is negligible. We formalize this intuition in Lemma 21. The proof of Lemma 21 is provided in the full version.

Lemma 21.

For each $i\in[r]$ , let $k_{i}$ denote the number of effective selectors among the first $i$ selectors $s_{1},\dots,s_{i}$ , and let $k_{0}=0$ . Then, for all $i\in[r]$ , we have that

\Pr\left[|H_{i}|>k_{i}\cdot\frac{r\ln(r/\varepsilon)}{\varepsilon}\,\middle|\,% \forall\,j\in\{0,\dots,i-1\},\,|H_{j}|\leq k_{j}\cdot\frac{r\ln(r/\varepsilon)% }{\varepsilon}\right]\leq\frac{\varepsilon}{r}.

(3)

We are ready to complete the proof of Lemma 19.

Proof of Lemma 19.

First, following the notations in Lemma 21, we upper bound the probability $\Pr\left[|H_{r}|\leq k_{r}\cdot\frac{r\ln(r/\varepsilon)}{\varepsilon}\right]$ as follows,

	$\displaystyle\Pr\left[\|H_{r}\|\leq k_{r}\cdot\frac{r\ln(r/\varepsilon)}{% \varepsilon}\right]$
$\displaystyle\geq$	$\displaystyle\Pr\left[\forall\,i\in[r],\,\|H_{i}\|\leq k_{i}\cdot\frac{r\ln(r/% \varepsilon)}{\varepsilon}\right]$
$\displaystyle=$	$\displaystyle\prod_{i\in[r]}\Pr\left[\|H_{i}\|\leq k_{i}\cdot\frac{r\ln(r/% \varepsilon)}{\varepsilon}\,\middle\|\,\forall\,j\in\{0,\dots,i-1\},\,\|H_{j}\|% \leq k_{j}\cdot\frac{r\ln(r/\varepsilon)}{\varepsilon}\right]$
$\displaystyle\geq$	$\displaystyle\left(1-\frac{\varepsilon}{r}\right)^{r}$
$\displaystyle\geq$	$\displaystyle\,1-\varepsilon.$	(4)

Moreover, we notice that the total number of effective selectors $k_{r}$ is at most $|I|$ , because any two distinct effective selectors $s_{i}$ and $s_{j}$ must satisfy that $\left\lfloor f(\{s_{i}\}|S_{i-1})\right\rfloor_{I}\neq\left\lfloor f(\{s_{j}\}% |S_{j-1})\right\rfloor_{I}$ (and there are only $|I|$ distinct values in the range of $\left\lfloor\cdot\right\rfloor_{I}$ ). Thus, Ineq. (3.2) implies that $\Pr\left[|H_{r}|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}\right]\geq 1-\varepsilon$ . The proof finishes by noticing that the set $H$ in Algorithm 1 is a subset of $H_{r}$ . $\hfill\blacktriangleleft$

3.3 The regular case: $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ and $|H|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$

Now we consider the regular case where $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ and $|H|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$ . To analyze this case, we first establish two simple claims. Claim 22 shows that w.h.p., the value of the optimal solution $O$ does not decrease significantly, when combined with any subset of elements in a small fraction of the random stream $\pi$ .

Claim 22.

For any $\eta,\delta\in[0,1]$ , let $V$ be a random subset of $[n]$ such that every element of $[n]$ appears in $V$ with probability at most $\delta$ (not necessarily independently). Then, with probability at least $1-\frac{\delta}{\eta}$ , it holds for all $X\subseteq V$ that $f(X|O)\geq-\eta\cdot f(O)$ .

Proof.

We define $g:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ such that $g(Y)=f(Y\cup O)$ for all $Y\subseteq[n]$ . Because $f$ is a non-negative submodular function, it follows that $g$ is also non-negative and submodular. Moreover, we define $X_{\min}:=\operatorname*{arg\,min}_{X\subseteq V}f(X|O)$ . Since $X_{\min}$ is a subset of $V$ and each element of $[n]$ appears in $V$ with probability at most $\delta$ , it follows that each element of $[n]$ appears in $X_{\min}$ with probability at most $\delta$ . Hence, by Lemma 14, we have that $\mathbb{E}[g(X_{\min})]\geq(1-\delta)\cdot g(\emptyset)$ , which is equivalent to $\mathbb{E}[f(X_{\min}|O)+f(O)]\geq(1-\delta)\cdot f(O)$ . By rearranging, we obtain that $\mathbb{E}[-f(X_{\min}|O)]\leq\delta\cdot f(O)$ . Then, by applying Markov’s inequality to the random variable $-f(X_{\min}|O)$ (note that this random variable is non-negative because $f(X_{\min}|O)\leq f(\emptyset|O)=0$ ), we have that

\Pr[-f(X_{\min}|O)\geq\eta\cdot f(O)]\leq\frac{\mathbb{E}[-f(X_{\min}|O)]}{% \eta\cdot f(O)}\leq\frac{\delta\cdot f(O)}{\eta\cdot f(O)}=\frac{\delta}{\eta}.

Thus, $f(X_{\min}|O)\geq-\eta\cdot f(O)$ holds with probability at least $1-\frac{\delta}{\eta}$ , which implies the claim. $\hfill\vartriangleleft$

Claim 23 bounds the error incurred by the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ . The proof is provided in the full version.

Claim 23.

Given $I=\{(1+\varepsilon)^{i}\cdot\gamma w\mid i\in\{0,...,\left\lceil\log_{1+% \varepsilon}(1/\gamma)\right\rceil\}\}$ with $w\geq 0$ and $\varepsilon,\gamma\in(0,1)$ , for any two real numbers $a\geq 0$ and $b\leq w$ , if $\left\lfloor a\right\rfloor_{I}\geq\left\lfloor b\right\rfloor_{I}$ , then we have that $a\geq(1-\varepsilon)b-\gamma w$ .

Next, we denote by $V_{\textnormal{final}}$ the set of elements that appear in the third phase of Algorithm 1, i.e., $V_{\textnormal{final}}:=\{\pi(i)\mid i=\left\lceil\varepsilon n\right\rceil+r% \cdot\left\lceil\frac{\varepsilon n}{r}\right\rceil+1,\dots,n\}$ . Recall that $X_{\textnormal{ALG}}$ denotes the solution set returned by Algorithm 1, and $O$ denotes the optimal solution. In Lemma 24, we show that $X_{\textnormal{ALG}}$ is almost a $\nicefrac{{1}}{{2}}$ approximation of $O\cap V_{\textnormal{final}}$ , conditioned on three high-probability events in the regular case.

Lemma 24.

Let $E_{1}$ and $E_{2}$ be the events defined in Lemma 18 and Lemma 19 respectively. Moreover, let $E_{3}$ denote the event that $f(X|O)\geq-\eta\cdot f(O)$ for all $X\subseteq\bigcup_{i=1}^{r}V_{i}$ , where $\eta:=\sqrt{\frac{2\varepsilon n+2r}{n}}$ . Suppose that the input parameter $\varepsilon$ for Algorithm 1 is in the range $\left(0,\frac{1}{2}\right)$ , and that $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ . Then, conditioned on events $E_{1},E_{2},E_{3}$ , Algorithm 1 guarantees that $\textstyle f(X_{\textnormal{ALG}})\geq\left(\frac{1}{2}-\varepsilon\right)% \cdot(f(O\cap V_{\textnormal{final}})-5\eta\cdot f(O))$ .

We provide the proofs of Lemma 24 and Theorem 16 in the full version. Here, we give a simplified proof sketch to illustrate the main idea.

Proof sketch.

To highlight the main idea, we make the simplifying assumption that both the set $S_{r}$ constructed in the second phase of Algorithm 1 and the optimal solution $O$ are bases of matroid ${\mathcal{M}}$ . We further assume that all elements in the optimal solution $O$ arrive in the third phase of Algorithm 1 (in reality, we expect a random $1-2\varepsilon$ fraction of them to appear in the third phase, which, by Lemma 13, accounts for $1-2\varepsilon$ fraction of the optimal value in expectation).

First, we partition the optimal solution into two sets: $O=O_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ , where $O_{L}:=O\setminus H$ and $O_{H}:=O\cap H$ . That is, $O_{H}$ contains the optimal elements that are included in $H$ by Algorithm 1, and $O_{L}$ consists of those that are not included in $H$ (note that conditioned on the high-probability event $E_{2}$ defined in Lemma 19, these elements were not added to $H$ because they did not satisfy the filter condition at Line 14 of Algorithm 1, not because of the break condition at Line 17). By Lemma 11, we can find a partition $S_{r}=S_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}$ such that $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ and $O_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}$ are also bases. Moreover, because both $S_{r}=S_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}$ and $O_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}$ are bases, by Lemma 12, there exists a bijection $h:S_{L}\to O_{L}$ such that for all $s_{i}\in S_{L}$ , substituting element $s_{i}$ in $S_{r}$ with element $h(s_{i})$ yields a new base. In particular, this implies that element $h(s_{i})$ could be added to set $S_{i-1}$ without violating the matroid constraint. Despite this, element $h(s_{i})\in O_{L}$ was not selected by the selector $s_{i}$ (since otherwise it would have been included in $H$ ). Thus, it must hold that $f(\{h(s_{i})\}|S_{i-1})\leq f(\{s_{i}\}|S_{i-1})$ (barring the rounding error incurred by the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ , which can be handled by Claim 23). Hence, we can derive that

$\displaystyle f(S_{L})$	$\displaystyle=\sum_{i\in[r]\textrm{ s.t.}\,s_{i}\in S_{L}}f(\{s_{i}\}\|S_{i-1}% \cap S_{L})$	(By telescoping sum)
	$\displaystyle\geq\sum_{i\in[r]\textrm{ s.t.}\,s_{i}\in S_{L}}f(\{s_{i}\}\|S_{i-% 1})$	(By submodularity)
	$\displaystyle\geq\sum_{i\in[r]\textrm{ s.t.}\,s_{i}\in S_{L}}f(\{h(s_{i})\}\|S_% {i-1})$
	$\displaystyle=\sum_{o\in O_{L}}f(\{o\}\|S_{i-1})$	(Since $h:S_{L}\to O_{L}$ is a bijection)
	$\displaystyle\geq f(O_{L}\|S_{i-1})\geq f(O_{L}\|S_{r})$	$\displaystyle\text{(By submodularity)}.$	(5)

Then, we consider the following two solution sets: $S_{r}$ and $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ . Recall that both $S_{r}$ and $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ are bases, and thus, they are feasible solutions. Moreover, both $S_{r}$ and $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ are subsets of $S_{r}\cup H$ , and hence, they are candidate solutions in the final exhaustive search of Algorithm 1. Now we lower bound the sum of the solution values of $S_{r}$ and $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ , as follows,
$\displaystyle f(S_{r})+f(S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H})$ $\displaystyle=f(S_{r})+f(S_{L})+f(O_{H}|S_{L})$ $\displaystyle\geq f(S_{r})+f(O_{L}|S_{r})+f(O_{H}|S_{L})$ (By Ineq. (3.3)) $\displaystyle\geq f(S_{r})+f(O_{L}|S_{r})+f(O_{H}|O_{L}\cup S_{r})$ (By submodularity and $S_{L}\subseteq S_{r}$ ) $\displaystyle=f(O\cup S_{r})$ (Since $O_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}=O$ ) $\displaystyle\geq(1-\eta)\cdot f(O),$

where the last inequality holds because of the event $E_{3}$ in the statement of Lemma 24 (which is a high-probability event by Claim 22) and the fact that $S_{r}\subseteq\bigcup_{i=1}^{r}V_{i}$ . It follows that one of $S_{r}$ and $S_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ must be a nearly $\nicefrac{{1}}{{2}}$ approximation of the optimal solution $O$ . This establishes Lemma 24.

To complete the proof of Theorem 16, we can assume w.l.o.g. that $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ (because otherwise Theorem 16 follows immediately from Lemma 17), and then combine Lemma 24 with the high-probability bounds we have established for events $E_{1},E_{2},E_{3}$ . $\hfill\blacktriangleleft$

4 Interlude: continuous greedy filtering

In this section, we present Continuous-Greedy-Filtering (Subroutine 2), a subroutine that will serve as a building block of our final $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation offline algorithm. Subroutine 2 combines the techniques used in our streaming algorithm (Algorithm 1) with a fast continuous greedy algorithm introduced by [4]. It operates in three phases.

Algorithm 2 Continuous-Greedy-Filtering

(f,{\mathcal{M}},r,\varepsilon)

.

Phase 1: Computing the highest singleton value

Subroutine 2 first identifies the element in $[n]$ with the highest singleton value and assigns this value to $v$ . Since Subroutine 2 is designed for the offline setting, $v$ can be computed exactly by iterating through all elements in $[n]$ .

Phase 2: Constructing a fractional solution using the continuous greedy algorithm

Then, Subroutine 2 uses the continuous greedy algorithm to construct a fractional solution from $\frac{r}{\varepsilon}$ subsampled sets: It runs for $\frac{1}{\varepsilon}$ epochs. In each epoch $t\in\left[\frac{1}{\varepsilon}\right]$ , it builds a new integral solution $S_{r}^{t}$ from scratch in $r$ steps. In each step $i\in[r]$ , it samples a small subset of elements $V_{i}^{t}$ . Among the elements in $V_{i}^{t}$ that can be added to the current integral solution without violating the matroid constraint, Subroutine 2 identifies the element with the highest “marginal value” (as specified at Line 11) with respect to the current fractional solution. If such an element exists and its marginal value is non-negative, Subroutine 2 includes it in the current integral solution and adds an $\varepsilon$ fraction of it to the current fractional solution.

Phase 3: Filtering all elements in $[n]$

Finally, Subroutine 2 filters all elements in $[n]$ , selecting a subset $H$ from them: For each element $e\in[n]$ , it adds element $e$ to $H$ if, for some step $i\in[r]$ of some epoch $t\in\left[\frac{1}{\varepsilon}\right]$ in the second phase, (i) element $e$ can be added to the integral solution at that step without violating the matroid constraint, and (ii) it has a strictly higher marginal value than element $s_{i}^{t}$ with respect to the fractional solution at that step (or has a strictly positive marginal value in case $s_{i}^{t}$ does not exist). Here, the marginal values are also compared after applying the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ with some well-chosen discretization $I$ , in order to keep the memory usage nearly linear in the matroid rank w.h.p. In the subroutine, we also impose a hard memory limit at Line 22. At the end of Subroutine 2, it returns the set $H$ , along with the union $\bigcup_{t=1}^{1/\varepsilon}S_{r}^{t}$ of all the integral solutions constructed during the second phase.

Now we let $O\in{\mathcal{M}}$ denote any optimal solution, and define $O_{H}:=O\cap H$ and $O_{L}:=O\setminus H$ (i.e., $O_{H}$ contains the optimal elements that are selected in the third phase of Subroutine 2, and $O_{L}$ consists of those that are not selected). In Theorem 25, we show that Subroutine 2 satisfies a property that is crucial for proving the $1-\nicefrac{{1}}{{e}}-\varepsilon$ approximation guarantee of our final algorithm.

Theorem 25.

Given any input submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ , matroid ${\mathcal{M}}\subseteq 2^{[n]}$ with rank $r\in{\mathbb{Z}}_{\geq 0}$ , and parameter $\varepsilon<\frac{1}{4}$ such that $\frac{1}{\varepsilon}\in{\mathbb{N}}^{+}$ , Subroutine 2 guarantees that with probability at least $1-2\varepsilon$ , there exists a solution set $X_{\textnormal{ALG}}\subseteq S$ such that $X_{\textnormal{ALG}}\in{\mathcal{M}}$ and

f(X_{\textnormal{ALG}})\geq\left(1-\frac{1}{e}\right)\cdot(f(O_{L})-8% \varepsilon\cdot f(O)),

where the set $S$ is the first output of Subroutine 2.

To prove Theorem 25, we assume w.l.o.g. that the matroid rank $r$ is non-zero, as the statement holds trivially if $r=0$ (we include this edge case in Theorem 25 because our final algorithm might invoke Subroutine 2 on a matroid with rank zero). We first establish Lemma 26, which shows that w.h.p., the break condition at Line 22 of Subroutine 2 is never reached. The proof of Lemma 26 relies on techniques similar to those developed in the proof of Lemma 19, which we defer to the full version.

Lemma 26.

Let $E_{1}$ denote the event that $|H|\leq\frac{r\ln(r/\varepsilon^{2})\cdot|I|}{\varepsilon^{4}}$ . Then, we have that $\Pr[E_{1}]\geq 1-\varepsilon$ .

Then, in Lemma 27, we show that conditioned on event $E_{1}$ and another high-probability event $E_{2}$ , the fractional solution $x^{1/\varepsilon}$ constructed in Subroutine 2 is a nearly $1-\frac{1}{e}$ approximation of $O_{L}$ .

Lemma 27.

Suppose that the input parameter $\varepsilon$ to Subroutine 2 is in the range $\left(0,\frac{1}{4}\right)$ . Let $E_{1}$ be the event defined in Lemma 26, and let $E_{2}$ denote the event that $f(X|O)\geq-\varepsilon\cdot f(O)$ for all $X\subseteq\bigcup_{t\in\left[\frac{1}{\varepsilon}\right],\,i\in[r]}V_{i}^{t}$ , where the sets $V_{i}^{t}$ are the subsampled sets in Subroutine 2. Then, conditioned on events $E_{1}$ and $E_{2}$ , Subroutine 2 guarantees that $F(x^{1/\varepsilon})\geq\left(1-\frac{1}{e}\right)\cdot(f(O_{L})-8\varepsilon% \cdot f(O))$ .

We defer the proof of Lemma 27 to the full version and provide a simplified proof sketch.

Proof sketch.

To illustrate the main idea, we make the simplifying assumption that the integral solution sets $S_{r}^{t}$ constructed in Subroutine 2 for all $t\in\left[\frac{1}{\varepsilon}\right]$ , and the optimal solution $O$ are all bases of matroid ${\mathcal{M}}$ .

Recall that the optimal solution $O$ is split into $O_{L}$ and $O_{H}$ , where $O_{H}$ contains the optimal elements that are included in $H$ by Subroutine 2, and $O_{L}$ consists of those that are not included in $H$ (note that conditioned on the high-probability event $E_{1}$ defined in Lemma 26, these elements were not added to $H$ because they did not satisfy the filter condition at Line 20 of Subroutine 2, not because of the break condition at Line 22). Given the partition $O=O_{L}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ , for each $t\in\left[\frac{1}{\varepsilon}\right]$ , we can find a partition $S_{r}^{t}=S_{L}^{t}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}^{t}$ such that $S_{L}^{t}\mathbin{\mathaccent 0{\cdot}\cup}O_{H}$ and $O_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}^{t}$ are also bases. Moreover, because both $S_{r}^{t}=S_{L}^{t}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}^{t}$ and $O_{L}\mathbin{\mathaccent 0{\cdot}\cup}S_{H}^{t}$ are bases, by Lemma 12, there exists a bijection $h_{t}:S_{L}^{t}\to O_{L}$ such that for all $s_{i}^{t}\in S_{L}^{t}$ , replacing element $s_{i}^{t}$ in $S_{r}^{t}$ with element $h_{t}(s_{i}^{t})$ results in a new base. In particular, this implies that element $h_{t}(s_{i}^{t})$ could be added to set $S_{i-1}^{t}$ without violating the matroid constraint. Despite this, element $h_{t}(s_{i}^{t})\in O_{L}$ did not satisfy the selection condition at Line 20 corresponding to $\Delta_{i}^{t}$ (since otherwise it would have been included in $H$ ). This implies that

F(\varepsilon\cdot\mathbf{1}_{h_{t}(s_{i}^{t})}|x^{t-1}+\varepsilon\cdot% \mathbf{1}_{S_{i-1}^{t}})\leq F(\varepsilon\cdot\Delta_{i}^{t}|x^{t-1}+% \varepsilon\cdot\mathbf{1}_{S_{i-1}^{t}})=F(\varepsilon\cdot\mathbf{1}_{s_{i}^% {t}}|x^{t-1}+\varepsilon\cdot\mathbf{1}_{S_{i-1}^{t}})

(6)

(ignoring the error incurred by the rounding operator $\left\lfloor\cdot\right\rfloor_{I}$ , which can be addressed by Claim 23). Now we derive that

	$\displaystyle\,F(x^{t})-F(x^{t-1})$		(7)
$\displaystyle=$	$\displaystyle\sum_{i\in[r]}F(\varepsilon\cdot\mathbf{1}_{s_{i}^{t}}\|x^{t-1}+% \varepsilon\cdot\mathbf{1}_{S_{i-1}^{t}})$	(By telescoping sum)
$\displaystyle\geq$	$\displaystyle\sum_{i\in[r]\textrm{ s.t.}\,s_{i}^{t}\in S_{L}^{t}}F(\varepsilon% \cdot\mathbf{1}_{s_{i}^{t}}\|x^{t-1}+\varepsilon\cdot\mathbf{1}_{S_{i-1}^{t}})$	(By the if condition at Line 10)
$\displaystyle\geq$	$\displaystyle\sum_{i\in[r]\textrm{ s.t.}\,s_{i}^{t}\in S_{L}^{t}}F(\varepsilon% \cdot\mathbf{1}_{h_{t}(s_{i}^{t})}\|x^{t-1}+\varepsilon\cdot\mathbf{1}_{S_{i-1}% ^{t}})$	(By Ineq. (6))
$\displaystyle\geq$	$\displaystyle\sum_{i\in[r]\textrm{ s.t.}\,s_{i}^{t}\in S_{L}^{t}}F(\varepsilon% \cdot\mathbf{1}_{h_{t}(s_{i}^{t})}\|x^{t})$	(By submodularity)
$\displaystyle=$	$\displaystyle\sum_{o\in O_{L}}F(\varepsilon\cdot\mathbf{1}_{o}\|x^{t})$	$\displaystyle\text{(Since $h_{t}:S_{L}^{t}\to O_{L}$ is a bijection)}.$	(8)

By Definition 4, $F(\varepsilon\cdot\mathbf{1}_{o}|x^{t})$ represents the additional value gained by increasing the probability of element $o$ appearing in the random set ${\mathcal{R}}(x^{t})$ by $\varepsilon$ , and thus, $F(\varepsilon\cdot\mathbf{1}_{o}|x^{t})=\varepsilon\cdot\mathbb{E}[f(\{o\}|{% \mathcal{R}}(x^{t})\setminus\{o\})]$ . Combining this with Ineq. (7), we obtain that

$\displaystyle F(x^{t})-F(x^{t-1})$	$\displaystyle\geq\sum_{o\in O_{L}}\varepsilon\cdot\mathbb{E}[f(\{o\}\|{\mathcal% {R}}(x^{t})\setminus\{o\})]$
	$\displaystyle\geq\sum_{o\in O_{L}}\varepsilon\cdot\mathbb{E}[f(\{o\}\|{\mathcal% {R}}(x^{t}))]$	(By submodularity)
	$\displaystyle\geq\varepsilon\cdot\mathbb{E}[f(O_{L}\|{\mathcal{R}}(x^{t}))]$	(By submodularity)
	$\displaystyle=\varepsilon\cdot(\mathbb{E}[f(O_{L}\cup{\mathcal{R}}(x^{t}))]-F(% x^{t}))$	(By Definition 4)
	$\displaystyle\geq\varepsilon\cdot(f(O_{L})-\varepsilon\cdot f(O)-F(x^{t})),$		(9)

where the last inequality follows because conditioned on event $E_{2}$ in the statement of Lemma 27, the random set ${\mathcal{R}}(x^{t})$ (which is always a subset of $\bigcup_{t\in\left[\frac{1}{\varepsilon}\right],\,i\in[r]}V_{i}^{t}$ in Subroutine 2) satisfies that $f({\mathcal{R}}(x^{t})|O)\geq-\varepsilon\cdot f(O)$ .

Then, by iteratively applying Ineq. (4) from $t=1$ to $t=\frac{1}{\varepsilon}$ (as in the analysis of the continuous greedy algorithm, with the difference being that the approximation guarantee here is with respect to $f(O_{L})-\varepsilon\cdot f(O)$ rather than $f(O)$ ), we can show that $F(x^{1/\varepsilon})\geq\left(1-\frac{1}{e}\right)\cdot(f(O_{L})-c\cdot% \varepsilon\cdot f(O))$ for some constant $c$ , which establishes Lemma 27. $\hfill\blacktriangleleft$

Finally, Theorem 25 follows by combining Lemma 27 with Lemma 26 and Claim 22.

Proof of Theorem 25.

We assume w.l.o.g. that the matroid rank $r$ is non-zero. First, we show that the event $E_{2}$ defined in Lemma 27 occurs w.h.p. Notice that in Subroutine 2, for any $t\in\left[\frac{1}{\varepsilon}\right]$ and $i\in[r]$ , the probability that an element $e\in[n]$ appears in the subsampled set $V_{i}^{t}$ is $\frac{\varepsilon^{3}}{r}$ . By a union bound, the probability that element $e$ appears in $\bigcup_{t\in\left[\frac{1}{\varepsilon}\right],\,i\in[r]}V_{i}^{t}$ is at most $\frac{r}{\varepsilon}\cdot\frac{\varepsilon^{3}}{r}=\varepsilon^{2}$ . Therefore, it follows from Claim 22 that event $E_{2}$ occurs with probability at least $1-\varepsilon$ . Then, combining this with Lemma 26 through a union bound, the probability that both events $E_{1}$ and $E_{2}$ occur is at least $1-2\varepsilon$ . Thus, by Lemma 27, it holds with probability at least $1-2\varepsilon$ that $F(x^{1/\varepsilon})\geq\left(1-\frac{1}{e}\right)\cdot(f(O_{L})-8\varepsilon% \cdot f(O))$ . This implies Theorem 25 by Lemma 15, because $x^{1/\varepsilon}=\sum_{t=1}^{1/\varepsilon}\varepsilon\cdot\mathbf{1}_{S_{r}^% {t}}$ and $S=\bigcup_{t=1}^{1/\varepsilon}S_{r}^{t}$ . $\hfill\blacktriangleleft$

On a separate note, Subroutine 2 itself does not guarantee a better-than- $\nicefrac{{1}}{{2}}$ approximation. This is because Subroutine 2 can be interpreted as an $\widetilde{{\mathcal{O}}}\left(\frac{r}{\textnormal{poly}(\varepsilon)}\right)$ -memory random-order streaming algorithm (by estimating the highest singleton value as in Algorithm 1 and replacing the subsampled sets with small segments of the random stream), and the hardness result by [26] asserts that such random-order streaming algorithms cannot exceed $\nicefrac{{1}}{{2}}$ approximation.

5 A $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation offline algorithm

In this section, we present our final algorithm (Algorithm 3) that achieves a nearly $1-\nicefrac{{1}}{{e}}$ approximation by recursively applying Continuous-Greedy-Filtering (Subroutine 2) to progressively refined instances. Specifically, Algorithm 3 performs a recursive process consisting of $\frac{1}{\alpha}$ levels.

Algorithm 3 Recursive-Continuous-Greedy-Filtering

(f,{\mathcal{M}},r,S^{\textnormal{acc}},O_{H}^{\textnormal{acc}},\alpha,k)

.

Initial phase

We initiate the first call to Algorithm 3 by setting $k=1$ , $S^{\textnormal{acc}}=\emptyset$ , and $O_{H}^{\textnormal{acc}}=\emptyset$ . We denote the optimal solution to the input instance $(f,{\mathcal{M}})$ by $O^{(1)}$ . At the root level $k=1$ , Algorithm 3 first invokes Subroutine 2 with parameter $\varepsilon=\alpha^{2}$ on the input instance $(f,{\mathcal{M}})$ , which returns two sets $S^{(1)}$ and $H^{(1)}$ . Then, Algorithm 3 enumerate all subsets of $H^{(1)}$ in the for loop at Line 9. Crucially, there will be an iteration of this loop where $O_{H}^{(1)}=O^{(1)}\cap H^{(1)}$ (all other iterations will be irrelevant to the analysis). Within this particular iteration (as well as in all other iterations), Algorithm 3 makes a recursive call to itself by setting $S^{\textnormal{acc}}=S^{(1)}$ and $O_{H}^{\textnormal{acc}}=O_{H}^{(1)}$ . These sets will be accumulated throughout the recursion.

Recursion phase

At each internal recursion level $k\in\{2,\dots,\frac{1}{\alpha}-1\}$ , Algorithm 3 receives the accumulated sets $S^{\textnormal{acc}}=\bigcup_{j=1}^{k-1}S^{(j)}$ and $O_{H}^{\textnormal{acc}}=\bigcup_{j=1}^{k-1}O_{H}^{(j)}$ from the previous $k-1$ levels. It first constructs a refined instance $(f^{(k)},{\mathcal{M}}^{(k)})$ , where the matroid ${\mathcal{M}}^{(k)}$ is the contraction of the original matroid ${\mathcal{M}}$ by the accumulated set $\bigcup_{j=1}^{k-1}O_{H}^{(j)}$ , and the non-negative submodular function $f^{(k)}$ is constructed by evaluating the original function $f$ on the union of the accumulated set $\bigcup_{j=1}^{k-1}O_{H}^{(j)}$ and the input set to $f^{(k)}$ . We define $O^{(k)}:=O^{(1)}\setminus\left(\bigcup_{j=1}^{k-1}O_{H}^{(j)}\right)$ . Next, Algorithm 3 calls Subroutine 2 with parameter $\varepsilon=\alpha^{2}$ on the instance $(f^{(k)},{\mathcal{M}}^{(k)})$ , which returns two sets $S^{(k)}$ and $H^{(k)}$ . Then, Algorithm 3 enumerates all subsets of $H^{(k)}$ . Crucially, there will be an iteration of this loop where $O_{H}^{(k)}=O^{(k)}\cap H^{(k)}$ (all other iterations will be irrelevant to the analysis). In this particular iteration (as well as in all other iterations), Algorithm 3 makes a recursive call to itself, passing the updated accumulated sets $S^{\textnormal{acc}}=\bigcup_{j=1}^{k}S^{(j)}$ and $O_{H}^{\textnormal{acc}}=\bigcup_{j=1}^{k}O_{H}^{(j)}$ as arguments.

It is important to keep in mind that, in the recursion tree of Algorithm 3 (illustrated in Figure 1), there is a unique root-to-leaf path such that for each $k\in\left[\frac{1}{\alpha}-1\right]$ , the $(k+1)$ -th call to Algorithm 3 along the path (corresponding to the $(k+1)$ -th node in the path) is invoked by the iterate $O_{H}^{(k)}=O^{(k)}\cap H^{(k)}$ (from the for loop at Line 9) during the $k$ -th call, where $O^{(k)}=O^{(1)}\setminus\left(\bigcup_{j=1}^{k-1}O_{H}^{(j)}\right)$ . We will focus on this particular path when we prove the approximation guarantee of Algorithm 3.

Figure 1: This figure shows an example depth-

2

recursion tree of Algorithm 3. The empty nodes form a unique path (made bold in the figure) in which, for each

k\in[2]

, the

(k+1)

-th call is invoked by the iterate

O_{H}^{(k)}=O^{(k)}\cap H^{(k)}

during the

k

-th call, where

O^{(k)}=O^{(1)}\setminus\left(\bigcup_{j=1}^{k-1}O_{H}^{(j)}\right)

.

Return phase

At the leaf level $k=\frac{1}{\alpha}$ , Algorithm 3 first calls Subroutine 2 on a refined instance $(f^{(1/\alpha)},{\mathcal{M}}^{(1/\alpha)})$ (constructed similarly to the instances in the previous levels), which returns two sets $S^{(1/\alpha)}$ and $H^{(1/\alpha)}$ . Then, it conducts an exhaustive search to find the most valuable subset $X_{\textnormal{ALG}}$ of $S^{\textnormal{acc}}\cup O_{H}^{\textnormal{acc}}=\left(\bigcup_{j=1}^{1/% \alpha}S^{(j)}\right)\cup\left(\bigcup_{j=1}^{1/\alpha-1}O_{H}^{(j)}\right)$ that belongs to matroid ${\mathcal{M}}$ , and returns $X_{\textnormal{ALG}}$ to the previous level. Then, at each level $k\in\left[\frac{1}{\alpha}-1\right]$ , among all solution sets returned by the recursive calls, Algorithm 3 identifies and returns the most valuable one to the previous level.

Time and space complexity

Now we analyze the time and space complexity of Algorithm 3 (assuming that we set $k=1$ , $S^{\textnormal{acc}}=\emptyset$ , and $O_{H}^{\textnormal{acc}}=\emptyset$ in the initial call). We first observe that at each level $k\in\left[\frac{1}{\alpha}\right]$ , the sets $S^{(k)}$ and $H^{(k)}$ , which are outputs of Subroutine 2 with parameter $\alpha^{2}$ , have sizes $|S^{(k)}|\leq\frac{r}{\alpha^{2}}$ (because $S^{(k)}$ is either the union of $\frac{1}{\alpha^{2}}$ solution sets constructed in the second phase of Subroutine 2 or an empty set) and $|H^{(k)}|={\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ (because of the break condition at Line 22 of Subroutine 2). From this, we observe the following:

(i)

At each leaf node of the recursion tree of Algorithm 3, the accumulated set $S^{\textnormal{acc}}=\bigcup_{k=1}^{1/\alpha}S^{(k)}$ has size $|S^{\textnormal{acc}}|\leq\frac{r}{\alpha^{3}}$ (because each set $S^{(k)}$ has size at most $\frac{r}{\alpha^{2}}$ ), and the accumulated set $O^{\textnormal{acc}}_{H}=\bigcup_{k=1}^{1/\alpha}O_{H}^{(k)}$ has size $|O^{\textnormal{acc}}_{H}|={\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{% poly}(\alpha)}\right)$ (because $|O_{H}^{(k)}|\leq|H^{(k)}|={\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{% poly}(\alpha)}\right)$ ).
(ii)

Each non-leaf node of the recursion tree has at most $2^{{\mathcal{O}}\big(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\big)}$ child nodes (because each set $H^{(k)}$ has size ${\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ ), which implies that the total number of leaves is $2^{{\mathcal{O}}\big(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\big)}$ , since the recursion tree has $\frac{1}{\alpha}$ levels in total.

Then, we notice that the runtime of each call to Subroutine 2 at each node is $n\cdot 2^{{\mathcal{O}}\left(r/\alpha^{2}\right)}$ , where the $2^{{\mathcal{O}}\left(r/\alpha^{2}\right)}$ factor accounts for the exact computation of the multi-linear extension (which, if desired, can be replaced by polynomial-time estimation using standard Monte-Carlo sampling). Moreover, the exhaustive search step at each leaf node takes $2^{{\mathcal{O}}\big(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\big)}$ time, since $|S^{\textnormal{acc}}|+|O^{\textnormal{acc}}_{H}|={\mathcal{O}}\left(\frac{r% \ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ . Hence, summing the runtime over all nodes, we obtain that the total runtime is $n\cdot 2^{{\mathcal{O}}\big(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\big)}$ . For the space complexity, we assume that Algorithm 3 traverses the recursion tree in depth-first order. We notice that at any node in any level $\ell\in\left[\frac{1}{\alpha}\right]$ of the recursion tree, Algorithm 3 only needs to store the sets $S^{(k)},H^{(k)},O_{H}^{(k)}$ for all $k\in[\ell]$ from its ancestor nodes and itself, and among $S^{(k)},H^{(k)},O_{H}^{(k)}$ , the set $H^{(k)}$ has the largest size, which is ${\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ . Therefore, the space complexity is ${\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ .

Next, in Theorem 28, we show that Algorithm 3 achieves a nearly $1-\nicefrac{{1}}{{e}}$ approximation. At a high level, the argument is as follows: Consider the specific path in the recursion tree of Algorithm 3, as illustrated in Figure 1, but with depth $\frac{1}{\alpha}$ for arbitrarily small $\alpha$ . Suppose that for all $k\in\left[\frac{1}{\alpha}\right]$ , the marginal value of the set $O^{(k)}_{H}$ with respect to $\bigcup_{j=1}^{k-1}O^{(j)}_{H}$ is at least $\alpha$ fraction of the optimal value, i.e., at least $\alpha\cdot f(O^{(1)})$ . Then, the union $\bigcup_{j=1}^{1/\alpha}O^{(j)}_{H}$ , which is a candidate solution in the exhaustive search step at the leaf node, must capture the entire optimal value. On the other hand, if for any $k\in\left[\frac{1}{\alpha}\right]$ , the marginal value of the set $O^{(k)}_{H}$ with respect to $\bigcup_{j=1}^{k-1}O^{(j)}_{H}$ is less than $\alpha$ fraction of the optimal value, then by submodularity, the set $O^{(1)}\setminus O^{(k)}_{H}$ should account for the majority of the optimal value. We can show that (using Theorem 28) w.h.p., the union of the set $\bigcup_{j=1}^{k-1}O^{(j)}_{H}$ and a subset of the first output of Subroutine 2 during the $k$ -th call along the path, which is a candidate solution in the exhaustive search step, is a nearly $1-\nicefrac{{1}}{{e}}$ approximation to $O^{(1)}\setminus O^{(k)}_{H}$ . The complete proof is provided in the full version.

Theorem 28.

Given any input submodular function $f:2^{[n]}\to{\mathbb{R}}_{\geq 0}$ , matroid ${\mathcal{M}}\subseteq 2^{[n]}$ with rank $r\in{\mathbb{N}}^{+}$ , and parameter $\alpha\in\left(0,\frac{1}{2}\right)$ such that $\frac{1}{\alpha}\in{\mathbb{N}}^{+}$ , by setting $S^{\textnormal{acc}}=\emptyset$ , $O_{H}^{\textnormal{acc}}=\emptyset$ , and $k=1$ , Algorithm 3 obtains a $1-\frac{1}{e}-7\alpha$ approximation with $n\cdot 2^{{\mathcal{O}}\big(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\big)}$ runtime and ${\mathcal{O}}\left(\frac{r\ln(r)^{2}}{\textnormal{poly}(\alpha)}\right)$ memory.

References

[1] Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular secretary problem with shortlists. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.1.
[2] Naor Alaluf, Alina Ene, Moran Feldman, Huy L Nguyen, and Andrew Suh. An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 47(4), 2022. doi:10.1287/moor.2021.1224.
[3] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014. doi:10.1145/2623330.2623637.
[4] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014. doi:10.1137/1.9781611973402.110.
[5] Richard A Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society, 1(2), 1969. doi:10.1017/S000497270004140X.
[6] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024. doi:10.1145/3618260.3649630.
[7] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014. doi:10.1137/1.9781611973402.106.
[8] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 2011. doi:10.1137/080733991.
[9] Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, 154, 2015. doi:10.1007/s10107-015-0900-7.
[10] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 2010. doi:10.1109/FOCS.2010.60.
[11] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight fpt approximations for k-median and k-means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
[12] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012. doi:10.1145/2213977.2214076.
[13] Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4), 2011. doi:10.1137/090779346.
[14] Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming submodular maximization under matroid constraints. Mathematics of Operations Research, 2025. doi:10.1287/moor.2023.0276.
[15] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Submodular Maximization Subject to Matroid Intersection on the Fly. In 30th Annual European Symposium on Algorithms (ESA 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.52.
[16] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. Journal of the ACM, 70(4), 2023. doi:10.1145/3588564.
[17] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011. doi:10.1137/1.9781611973082.83.
[18] Curtis Greene. A multiple exchange property for bases. Proceedings of the American Mathematical Society, 39(1), 1973. doi:10.1090/S0002-9939-1973-0311494-8.
[19] Chien Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. SIAM Journal on Discrete Mathematics, 2022. doi:10.1137/20M1357317.
[20] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference on Machine Learning. PMLR, 2019. URL: https://proceedings.mlr.press/v97/kazemi19a.html.
[21] Paul Liu, Aviad Rubinstein, Jan Vondrák, and Junyao Zhao. Cardinality constrained submodular maximization for random streams. Advances in Neural Information Processing Systems, 34, 2021. URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/333222170ab9edca4785c39f55221fe7-Paper.pdf.
[22] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2020. doi:10.1137/1.9781611975994.5.
[23] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/aaai.v32i1.11529.
[24] George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3), 1978. doi:10.1287/moor.3.3.177.
[25] Benjamin Qi. On maximizing sums of non-monotone submodular and linear functions. Algorithmica, 86(4), 2024. doi:10.1007/s00453-023-01183-3.
[26] Aviad Rubinstein and Junyao Zhao. Maximizing non-monotone submodular functions over small subsets: Beyond 1/2-approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.106.
[27] Mohammad Shadravan. Improved submodular secretary problem with shortlists. arXiv preprint arXiv:2010.01901, 2020. arXiv:2010.01901.
[28] Piotr Skowron. FPT approximation schemes for maximizing submodular functions. Information and Computation, 257, 2017. doi:10.1016/j.ic.2017.10.002.
[29] Douglas R Woodall. An exchange theorem for bases of matroids. Journal of Combinatorial Theory, Series B, 16(3), 1974. doi:10.1016/0095-8956(74)90067-7.

[bib.bib1] [1] Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular secretary problem with shortlists. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.1.

[bib.bib2] [2] Naor Alaluf, Alina Ene, Moran Feldman, Huy L Nguyen, and Andrew Suh. An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 47(4), 2022. doi:10.1287/moor.2021.1224.

[bib.bib3] [3] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014. doi:10.1145/2623330.2623637.

[bib.bib4] [4] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014. doi:10.1137/1.9781611973402.110.

[bib.bib5] [5] Richard A Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society, 1(2), 1969. doi:10.1017/S000497270004140X.

[bib.bib6] [6] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024. doi:10.1145/3618260.3649630.

[bib.bib7] [7] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014. doi:10.1137/1.9781611973402.106.

[bib.bib8] [8] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 2011. doi:10.1137/080733991.

[bib.bib9] [9] Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, 154, 2015. doi:10.1007/s10107-015-0900-7.

[bib.bib10] [10] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 2010. doi:10.1109/FOCS.2010.60.

[bib.bib11] [11] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight fpt approximations for k-median and k-means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.

[bib.bib12] [12] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012. doi:10.1145/2213977.2214076.

[bib.bib13] [13] Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4), 2011. doi:10.1137/090779346.

[bib.bib14] [14] Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming submodular maximization under matroid constraints. Mathematics of Operations Research, 2025. doi:10.1287/moor.2023.0276.

[bib.bib15] [15] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Submodular Maximization Subject to Matroid Intersection on the Fly. In 30th Annual European Symposium on Algorithms (ESA 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.52.

[bib.bib16] [16] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. Journal of the ACM, 70(4), 2023. doi:10.1145/3588564.

[bib.bib17] [17] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011. doi:10.1137/1.9781611973082.83.

[bib.bib18] [18] Curtis Greene. A multiple exchange property for bases. Proceedings of the American Mathematical Society, 39(1), 1973. doi:10.1090/S0002-9939-1973-0311494-8.

[bib.bib19] [19] Chien Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. SIAM Journal on Discrete Mathematics, 2022. doi:10.1137/20M1357317.

[bib.bib20] [20] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference on Machine Learning. PMLR, 2019. URL: https://proceedings.mlr.press/v97/kazemi19a.html.

[bib.bib21] [21] Paul Liu, Aviad Rubinstein, Jan Vondrák, and Junyao Zhao. Cardinality constrained submodular maximization for random streams. Advances in Neural Information Processing Systems, 34, 2021. URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/333222170ab9edca4785c39f55221fe7-Paper.pdf.

[bib.bib22] [22] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2020. doi:10.1137/1.9781611975994.5.

[bib.bib23] [23] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/aaai.v32i1.11529.

[bib.bib24] [24] George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3), 1978. doi:10.1287/moor.3.3.177.

[bib.bib25] [25] Benjamin Qi. On maximizing sums of non-monotone submodular and linear functions. Algorithmica, 86(4), 2024. doi:10.1007/s00453-023-01183-3.

[bib.bib26] [26] Aviad Rubinstein and Junyao Zhao. Maximizing non-monotone submodular functions over small subsets: Beyond 1/2-approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.106.

[bib.bib27] [27] Mohammad Shadravan. Improved submodular secretary problem with shortlists. arXiv preprint arXiv:2010.01901, 2020. arXiv:2010.01901.

[bib.bib28] [28] Piotr Skowron. FPT approximation schemes for maximizing submodular functions. Information and Computation, 257, 2017. doi:10.1016/j.ic.2017.10.002.

[bib.bib29] [29] Douglas R Woodall. An exchange theorem for bases of matroids. Journal of Combinatorial Theory, Series B, 16(3), 1974. doi:10.1016/0095-8956(74)90067-7.

Fixed-Parameter Tractable Submodular Maximization over a Matroid

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Theorem 1 (Restatement of Theorem 28).

Theorem 2 (Restatement of Theorem 16).

1.1 Overview of our approach

Continuous greedy filtering

(𝟏−𝟏/𝒆−𝜺)-approximation: a recursive approach

(𝟏/𝟐−𝜺)-approximation semi-streaming algorithm: single-epoch filtering

Comparison to [26]

1.2 Additional related work

FPT submodular maximization

Streaming submodular maximization

2 Preliminaries

2.1 Submodular functions and matroids

Definition 3 (submodular function).

Definition 4 (multi-linear extension).

Definition 5 (matroid).

Definition 6 (rank).

Definition 7 (base).

Definition 8 (restriction).

Definition 9 (contraction).

2.2 Random-order streaming model

2.3 Other useful notions and lemmata

Definition 10 (rounding operator).

Lemma 11 ([18, 29]).

Lemma 12 ([5]).

Lemma 13 ([13, Lemma 2.2]).

Lemma 14 ([7, Lemma 2.2]).

Lemma 15.

3 A (𝟏/𝟐−𝜺)-approximation random-order streaming algorithm

Phase 1: Estimating the highest singleton value

Phase 2: Greedily constructing a solution set

Phase 3: Filtering the remaining stream

Theorem 16.

3.1 The simple case: 𝐦𝐚𝐱𝒆∈[𝒏]⁡𝒇⁢({𝒆})≥𝒓𝜺⋅𝐦𝐢𝐧𝒆∈𝑻⁡𝒇⁢({𝒆})

Lemma 17.

Lemma 18.

3.2 The unlikely case: |𝑯|>𝒓⁢𝐥𝐧⁡(𝒓/𝜺)⋅|𝑰|𝜺

Lemma 19.

Claim 20.

Proof.

Lemma 21.

Proof of Lemma 19.

3.3 The regular case: 𝐦𝐚𝐱𝒆∈[𝒏]⁡𝒇⁢({𝒆})<𝒓𝜺⋅𝐦𝐢𝐧𝒆∈𝑻⁡𝒇⁢({𝒆}) and |𝑯|≤𝒓⁢𝐥𝐧⁡(𝒓/𝜺)⋅|𝑰|𝜺

Claim 22.

Proof.

Claim 23.

Lemma 24.

Proof sketch.

4 Interlude: continuous greedy filtering

Phase 1: Computing the highest singleton value

Phase 2: Constructing a fractional solution using the continuous greedy algorithm

Phase 3: Filtering all elements in [𝒏]

Theorem 25.

Lemma 26.

Lemma 27.

Proof sketch.

Proof of Theorem 25.

5 A (𝟏−𝟏/𝒆−𝜺)-approximation offline algorithm

Initial phase

Recursion phase

Return phase

Time and space complexity

Theorem 28.

References

$(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation: a recursive approach

$(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation semi-streaming algorithm: single-epoch filtering

3 A $(\nicefrac{{1}}{{2}}-\varepsilon)$ -approximation random-order streaming algorithm

3.1 The simple case: $\max_{e\in[n]}f(\{e\})\geq\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$

3.2 The unlikely case: $|H|>\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$

3.3 The regular case: $\max_{e\in[n]}f(\{e\})<\frac{r}{\varepsilon}\cdot\min_{e\in T}f(\{e\})$ and $|H|\leq\frac{r\ln(r/\varepsilon)\cdot|I|}{\varepsilon}$

Phase 3: Filtering all elements in $[n]$

5 A $(1-\nicefrac{{1}}{{e}}-\varepsilon)$ -approximation offline algorithm