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.
Shu-Yu Bao, Qing-Qin Nong, Su-Ning Gong
. An Improved Space Semi-Streaming Algorithm for Submodular Maximization under b-Matching Constraint[J]. Journal of the Operations Research Society of China, 2026
, 14(2)
: 671
-686
.
DOI: 10.1007/s40305-024-00543-2
[1] Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766(2011)
[2] Chekuri, C., Gupta, S., Quanrud, K.: Streaming algorithms for submodular function maximization. In: ICALP, pp. 318–330(2015)
[3] Crouch, M., Stubbs, D.M.: Improved streaming algorithms for weighted matching, via unweighted matching. In: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 96–104(2014)
[4] Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discret. Math. 25(3–4), 1251–1265(2011)
[5] Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoret. Comput. Sci. 348(2), 207–216(2005)
[6] Feldman, M., Karbasi, A., Kazemi, E.: Do less, get more: streaming submodular maximization with subsampling. In: NeurIPS, pp. 732–742(2018)
[7] Feldman, M., Naor, J.S., Schwartz, R., Ward, J.: Improved approximations for k-exchange systems. In: ESA, pp. 784–798(2011)
[8] Ghaffari, M., Wajc, D.: Simplified and space-optimal semi-streaming (2+ε)-approximate matching, arXiv:1701.03730(2018)
[9] Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197(1981)
[10] Huang, C.-C., Sellier, F.: Semi-streaming algorithms for submodular function maximization under b-matching, matroid and matchoid constraints. arXiv:2107.13071(2022)
[11] Krause, A., Guestrin, C.: Near-optimal nonmyopic value of information in graphical models. Comput. Sci. 35(1), 324–331(2011)
[12] Levin, R., Wajc, D.: Streaming submodular matching meets the primal-dual method. In: SODA, pp. 1914–1933(2021)
[13] Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (HLT), vol. 1, pp. 510–520(2011)
[14] McGregor, A.: Finding graph matchings in data streams. In: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 170–181(2005)
[15] Paz, A., Schwartzman, G.: A (2+ ε)-approximation for maximum weight matching in the semistreaming model. In: SODA, pp. 2153–2161(2017)
[16] Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer (2003)
[17] Singer, Y.: How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In: Proceedings of the 5th ACM International Conference on Web Search and Data Mining (WSDM), pp. 733–742(2012)
[18] Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: Proceedings of the 31st International Conference on Machine Learning (PMLR), vol. 32, pp. 351–359(2014)
[19] Zelke, M.: Weighted matching in the semi-streaming model. In: STACS, pp. 669–680(2008)
