Streaming Algorithms for Maximizing k-Submodular Functions with the Multi-knapsack Constraint

doi:10.1007/s40305-024-00544-1

Abstract

Abstract: The problem of maximizing submodular functions with constraints has attracted widespread attention in the past few decades. In recent years, the extensions of submodular functions were studied, such as lattice submodular functions, diminishing return submodular (DR-submodular) functions and $k$-submodular functions. A $k$ submodular function is a generalization of a submodular function to $k$ dimensions. Many machine learning problems can be cast as $k$-submodular maximization problems, for example, influence maximization with $k$ kinds of topics and sensor placement with $k$ kinds of sensors. Recently, the unprecedented growth in modern datasets makes it necessary to design streaming algorithms. This paper investigates the problem of maximizing a nonnegative normalized $k$-submodular function with the multi-knapsack constraint (also called the $d$-knapsack constraint) in the streaming model. To address this problem, we design an efficient streaming algorithm that runs in one pass, stores at most $O\left(\frac{b \log b}{\varepsilon}\right)$ elements and queries at most $O\left(\frac{d k \log b}{\varepsilon}\right)$ per element where $b$ is a constant after the normalization of the problem. This streaming algorithm also can achieve a $\left(\frac{1}{2(1+d)}-\varepsilon\right)$-approximation when the objective function $f$ is monotone and $\left(\frac{1}{3+2 d}-\varepsilon\right)$-approximation when the objective function $f$ is non-monotone.

Key words: k-Submodular maximization, Multi-knapsack constraint, Streaming algorithm, Approximation algorithm

CLC Number:

Shu-Fang Gong, Bin Liu, Qi-Zhi Fang. Streaming Algorithms for Maximizing k-Submodular Functions with the Multi-knapsack Constraint[J]. Journal of the Operations Research Society of China, 2026, 14(1): 325-343.

TrendMD

References

[1] Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: The Proceedings of the Twentieth International Conference on Knowledge Discovery and Data Mining, pp. 671-680. ACM Press, New York (2014)
[2] Breuer, A., Balkanski, E., Singer, Y.: The FAST algorithm for submodular maximization. In: The Proceedings of the Thirty-Seventh International Conference on Machine Learning, pp. 1134-1143. PMLR Press, Virtual Event (2020)
[3] Chekuri, C., Quanrud, K.: Parallelizing greedy for submodular set function maximization in matroids and beyond. In: The Proceedings of the Fifty-First Annual ACM SIGACT Symposium on Theory of Computing, pp. 78-89. ACM Press, Phoenix (2019)
[4] Ene, A., Nguyen, H. L., Vladu, A.: A parallel double greedy algorithm for submodular maximization (2018). arXiv:1812.01591
[5] Ene, A., Nguyen, H. L.: A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In: The Proceedings of the Forty-Sixth International Colloquium on Automata, Languages, and Programming, pp. 53:1-53:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik Press, Patras (2019)
[6] Huber, A., Kolmogorov, V.: Towards minimizing k-submodular functions. In: The Proceedings of the Combinatorial Optimization: Second International Symposium, pp. 451-462. Springer Press, Athens (2012)
[7] Iwata, S.,Tanigawa, S. and Yoshida, Y.: Improved approximation algorithms for k-submodular function maximization. In: The Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404-413. SIAM Press, Arlington (2016)
[8] Ko, C.-W., Lee, J., Queyranne, M.: An exact algorithm for maximum entropy sampling. Oper. Res. 43(4), 684-691(1995)
[9] Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the Spread of Influence through a Social Network. In: The Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining, pp. 137-146. ACM Press, Washington (2003)
[10] Krause, A., Leskovec, J., Isovitsch, S., Xu, J., Guestrin, C., VanBriesen, J., Small, M., Fischbeck, P.: "Optimizing sensor placements in water distribution systems using submodular function maximization. In: The Proceedings of the Eighth Annual Water Distribution Systems Analysis, pp. 1-17. Cincinnati (2008)
[11] Lovász, L.: Submodular functions and convexity. In: The Proceedings of the XIth International Symposium on Mathematical Programming. pp. 235-257. Springer Press, Bonn (1982)
[12] Liu, M., Tuzel, O., Ramalingam, S., Chellappa, R.: Entropy-rate clustering: Cluster analysis via maximizing a submodular function subject to a matroid constraint. IEEE Trans. Pattern Anal. Mach. Intell. 36(1), 99-112(2013)
[13] Nguyen, L., Thai, M.T.: Streaming k-submodular maximization under noise subject to size constraint. In: The Proceedings of the Thirty-Seventh International Conference on Machine Learning, pp. 7338- 7347. PMLR Press, Virtual Event (2020)
[14] Ohsaka, N., Yoshida, Y.: Monotone k-submodular function maximization with size constraints. In: The Proceedings of the Twenty-Eighth Advances in Neural Information Processing Systems, pp. 694-702. Montreal (2015)
[15] Oshima, H.: Improved randomized algorithm for k-submodular function maximization. SIAM J. Discret. Math. 35(1), 1-22(2021)
[16] Pham, C.V., Vu, Q.C., Ha, D.K.T., Nguyen, T.T., Le, N.D.: Maximizing k-submodular functions under budget constraint: applications and streaming algorithms. J. Comb. Optim. 44(1), 723-751(2022)
[17] Qian, C., Shi, J., Tang, K., Zhou, Z.: Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. SIAM J. Discret. Math. 22(4), 595-608(2018)
[18] Rafiey, A., Yoshida, Y.: Fast and private submodular and k-submodular functions maximization with matroid constraints. In: The Proceedings of the Thirty-Seventh International Conference on Machine Learning, pp. 7887-7897. PMLR Press, Virtual Event (2020)
[19] Singh, A., Guillory, A., Bilmes, J.: On bisubmodular maximization. In: The Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pp. 1055-1063. PMLR Press, La Palma (2012)
[20] Sakaue, S.: Onmaximizing amonotonek-submodularfunction subject to amatroid constraint. Discret. Optim. 23, 105-113(2017)
[21] Sun, X., Xu, D., Guo, L., Li, M.: Deterministic approximation algorithm for submodular maximization subject to a matroid constraint. Theor. Comput. Sci. 890, 1-15(2021)
[22] Sun, Y., Liu, Y., Li, M.: Maximization of k-submodular function with a matroid constraint. In: The Proceedings of the Seventeenth Annual Conference Theory and Applications of Models of Computation, pp. 1-10. Springer Press, Tianjin (2022)
[23] Tang, Z., Wang, C., Chan, H.: On maximizing a monotone k-submodular function under a knapsack constraint. Oper. Res. Lett. 50(1), 28-31(2022)
[24] Ward, J., Živny, S.: Maximizing k-submodular functions and beyond. ACM Trans. Algorithms 12(4), 1-26(2016)
[25] Wang, B., Zhou, H.: Multilinear extension of k-submodular functions (2021). arXiv:2107.07103
[26] Yu, Q., Xu, L., Cui, S.: Streaming algorithms for news and scientific literature recommendation: monotone submodular maximization with a d-knapsack constraint. IEEE Access 6, 53736-53747(2018)
[27] Zhang, Y., Li, M., Yang, D., Xue, G.: A budget feasible mechanism for k-topic influence maximization in social networks. In: The Proceedings of the 2019 IEEE Global Communications Conference, pp. 1-6. Waikoloa (2019)
[28] Zhang, Z., Liu, B., Wang, Y., Xu, D., Zhang, D.: Maximizing a monotone non-submodular function under a knapsack constraint. IEEE Trans. Pattern Anal. Mach. Intell. 43(5), 1125-1148(2022)
[29] Zhang, Z., Du, D., Ma, R., Wu, D.: Maximizing the differences between a monotone DR-submodular function and a linear function on the integer lattice. J. Oper. Res. Soc. China 6, 1-13(2022)