Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain “sparsifer”: a subset of elements, of size O(|Sopt| · 1/ɛ), where Sopt denotes the optimal solution, that is guaranteed to contain a 3/2 + ɛ approximation, while guaranteeing certain robustness properties. We call such a small subset a Density Constrained Subset (DCS), which is inspired by the Edge-Degree Constrained, Subgraph, (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the density-based decomposition. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.

In this paper, we introduce the concept of Density-Balanced Subset in a matroid, in which independent sets can be sampled so as to guarantee that (i) each element has the same probability to be sampled, and (ii) those events are negatively correlated. These Density-Balanced Subsets are subsets in the ground set of a matroid in which the traditional notion of uniform random sampling can be extended. We then provide an application of this concept to the Matroid-Constrained Maximum Coverage problem. In this problem, given a matroid $\mathcal{M} = (V, \mathcal{I})$ of rank $k$ on a ground set $V$ and a coverage function $f$ on $V$, the goal is to find an independent set $S \in \mathcal{I}$ maximizing $f(S)$. This problem is an important special case of the much-studied submodular function maximization problem subject to a matroid constraint; this is also a generalization of the maximum $k$-cover problem in a graph. In this paper, assuming that the coverage function has a bounded frequency $μ$ (i.e., any element of the underlying universe of the coverage function appears in at most $μ$ sets), we design a procedure, parameterized by some integer $ρ$, to extract in polynomial time an approximate kernel of size $ρ\cdot k$ that is guaranteed to contain a $1 - (μ- 1)/ρ$ approximation of the optimal solution. This procedure can then be used to get a Fixed-Parameter Tractable Approximation Scheme (FPT-AS) providing a $1 - \varepsilon$ approximation in time $(μ/\varepsilon)^{O(k)} \cdot |V|^{O(1)}$. This generalizes and improves the results of [Manurangsi, 2019] and [Huang and Sellier, 2022], providing the first FPT-AS working on an arbitrary matroid. Moreover, because of its simplicity, the kernel construction can be performed in the streaming setting.

We consider the maximum weight $b$-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from $[1,W]$, we present a $2 - \frac{1}{2W} + \varepsilon$ approximation algorithm, using a memory of $O(\max(|M_G|, n) \cdot poly(\log(m),W,1/\varepsilon))$, where $|M_G|$ denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Bernstein, 2015], which achieves a $3/2 + \varepsilon$ approximation for the maximum cardinality simple matching. When $W$ is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a $2 - δ$ approximation (for some small constant $δ\sim 10^{-17}$) for the maximum weight simple matching. In particular, for the weighted $b$-matching problem, ours is the first result beating the approximation ratio of $2$. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Bernstein and Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a $2 - \frac{1}{2W} + \varepsilon$ approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry's duality theorem.

We consider the problem of maximizing a submodular function under the b-matching constraint, in the semi-streaming model. Our main results can be summarized as follows. - When the function is linear, i.e. for the maximum weight b-matching problem, we obtain a 2+ε approximation. This improves the previous best bound of 3+ε [Roie Levin and David Wajc, 2021]. - When the function is a non-negative monotone submodular function, we obtain a 3 + 2 √2 ≈ 5.828 approximation. This matches the currently best ratio [Roie Levin and David Wajc, 2021]. - When the function is a non-negative non-monotone submodular function, we obtain a 4 + 2 √3 ≈ 7.464 approximation. This ratio is also achieved in [Roie Levin and David Wajc, 2021], but only under the simple matching constraint, while we can deal with the more general b-matching constraint. We also consider a generalized problem, where a k-uniform hypergraph is given with an extra matroid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. We extend our technique to this case to obtain an algorithm with an approximation of 8/3k+O(1). Our algorithms build on the ideas of the recent works of Levin and Wajc [Roie Levin and David Wajc, 2021] and of Garg, Jordan, and Svensson [Paritosh Garg et al., 2021]. Our main technical innovation is to introduce a data structure and associate it with each vertex and the matroid, to record the extra information of the stored edges. After the streaming phase, these data structures guide the greedy algorithm to make better choices.