A Semi-streaming Algorithm for Monotone Regularized Submodular Maximization with a Matroid Constraint

doi:10.1007/s40305-023-00525-w

Abstract

Abstract: In the face of large-scale datasets in many practical problems, it is an effective method to design approximation algorithms for maximizing a regularized submodular function in a semi-streaming model. In this paper, we study the monotone regularized submodular maximization with a matroid constraint and present a single-pass semistreaming algorithm using multilinear extension function and greedy idea. We show that our algorithm has an approximation ratio of $\left(\frac{(\beta-1)\left(1-\mathrm{e}^{-\alpha}\right)}{\beta+\alpha \beta-\alpha}, \frac{\beta(\beta-1)\left(1-\mathrm{e}^{-\alpha}\right)}{\beta+\alpha \beta-\alpha}\right)$ and a memory of $O(r(M))$, where $r(M)$ is the rank of the matroid and parameters $\alpha, \beta>1$. Specifically, if $\alpha=1.18$ and $\beta=9.784$, our algorithm is ( $0.302,2.955$ )-approximate. If $\alpha=1.257$ and $\beta=3.669$, our algorithm is $(0.2726,1)$-approximate.

Key words: Regularized Submodular Maximization, Possible Negative Objective, Matroid Constraint, Semi-Streaming Algorithm

CLC Number:

Qing-Qin Nong, Yue Wang, Su-Ning Gong. A Semi-streaming Algorithm for Monotone Regularized Submodular Maximization with a Matroid Constraint[J]. Journal of the Operations Research Society of China, 2026, 14(1): 162-178.

TrendMD

References

[1] Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Chekuri, C. (ed.) Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433-1452. Society for Industrial and Applied Mathematics, Philadelphia, PA (2014)
[2] Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Lin, D., Matsumoto, Y., Mihalcea, R. (eds.) The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510-520. Association for Computer Linguistics, New York (2011)
[3] Hartline, J., Mirrokni, V., Sundararajan, M.: Optimal marketing strategies over social networks. In: Huai, J., Chen, R., Hon, H.W. (eds.) Proceedings of the 17th International Conference on World Wide Web, pp. 189-198. Association for Computing Machinery, New York, (2008)
[4] Kazemi, E., Minaee, S., Feldman, M., Karbasi, A.: Regularized submodular maximization at scale. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning, vol. 139, pp. 5356-5366. PMLR, New York (2021)
[5] Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425-440(1991)
[6] Wang, Y., Xu, D., Du, D., Ma, R.: Bicriteria algorithms to balance coverage and cost in team formation under online model. Theoret. Comput. Sci. 854, 68-76(2021)
[7] Feldman, M., Liu, P., Norouzi-Fard, A., Svensson, O., Zenklusen, R.: Streaming submodular maximization under matroid constraints. In: Bojá nczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, vol. 59, pp. 1-20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl (2022)
[8] Lu, C., Yang, W., Gao, S.: Regularized non-monotone submodular maximization. CoRR abs/2103.10008(2021)
[9] Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197-1218(2017)
[10] Feldman, M.: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853-878(2021)
[11] Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 2634-2643. PMLR, New York (2019)
[12] Nikolakaki, S.M., Ene, A., Terzi, E.: An efficient framework for balancing submodularity and cost. In: Zhu, F., Ooi, B.C., Miao, C. (eds.) Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1256-1266. Association for Computing Machinery, New York (2021)
[13] Gong, Q., Gao, S., Wang, F., Yang, R.: A multi-pass streaming algorithm for regularized submodular maximization. In: Du, D., Du, D., Wu, C., Xu, D. (eds.) Combinatorial Optimization and Applications, pp. 701-711. Springer, Cham (2021)
[14] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Program. 14, 265-294(1978)
[15] Calinescu, G., Chekuri, C., Pal, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740-1766(2011)
[16] Edmonds, J.: Matroids, submodular functions and certain polyhedra. Combinatorial Structures and Their Applications, pp. 69-87(1970)
[17] Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 182-196. Springer, Berlin, Heidelberg (2007)