Abstract: Let $G=(V, E)$ be a multi-graph without self-loops where each vertex $v \in V$ has a capacity $b_v \in \mathbb{Z}_{+}$. A $b$-matching is a subset of edges $M \subseteq E$ such that each vertex $v$ is incident with at most $b_v$ edges in $M$ and each edge can be selected at most once. We study monotone submodular maximization subject to $b$-matching constraint (Monotone $\mathrm{MS}_{\mathrm{B}} \mathrm{M}$ ) in the semi-streaming model. There is a trade-off between the space complexity and the approximation ratio of the algorithms of the Monotone $\mathrm{MS}_{\mathrm{B}} \mathrm{M}$. In a recent breakthrough, Levin and Wajc give a 5.828 approximate algorithm for this problem and it needs to store $O\left(\sum_{v \in V} b_v \log n\right)$ edges in memory. In this paper, we present an improved space algorithm that contains $O\left(\sum_{v \in V} \max \left\{b_v \cdot \log \left(\frac{b_v}{\varepsilon}\right), b_v^{\frac{3}{2}} \cdot \log \left(\frac{1}{\varepsilon}\right)\right\}\right)$ edges in memory by introducing queues with size limits for the vertices and its approximation ratio is 6.2.

Key words: Submodular, b-Matching, Semi-streaming, Space complexity, Primal–dual