Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint.

We consider the problem of maximizing a non-negative submodular function under the $b$-matching constraint, in the semi-streaming model. When the function is linear, monotone, and non-monotone, we obtain the approximation ratios of $2+\varepsilon$, $3 + 2 \sqrt{2} \approx 5.828$, and $4 + 2 \sqrt{3} \approx 7.464$, respectively. We also consider a generalized problem, where a $k$-uniform hypergraph is given, along 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 $\frac{8}{3}k+O(1)$.