Approximation Algorithms for k-Submodular Maximization Subject to a Knapsack Constraint

doi:10.1007/s40305-024-00539-y

Abstract

Abstract: In this paper, we study the problem of maximizing $k$-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a $\frac{1}{2}\left(1-\mathrm{e}^{-2}\right) \approx$ 0.432 greedy approximation algorithm, improving the previous best-known ratio $\frac{1}{2}(1- \left.\mathrm{e}^{-1}\right) \approx 0.316$. We also consider the non-monotone knapsack problem and provide two algorithms. The first is a greedy-type combinatorial algorithm with approximation ratio $\frac{1}{3}\left(1-\mathrm{e}^{-3}\right) \approx 0.317$, while the second is a multilinear-extension-based algorithm with approximation ratio $\frac{1}{3}-\varepsilon$, where $\varepsilon>0$.

Key words: k-submodular, Knapsack, Approximation algorithm

CLC Number:

68W25
90C27

Hao Xiao, Qian Liu, Yang Zhou, Min Li. Approximation Algorithms for k-Submodular Maximization Subject to a Knapsack Constraint[J]. Journal of the Operations Research Society of China, 2026, 14(2): 397-412.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00539-y

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/397

References

[1] Ene, A., Nguyen, H.: Streaming algorithm for monotone k-submodular maximization with cardinality constraints. In: Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., & Sabato, S. (Eds.), Proceedings of the 39th International Conference on Machine Learning, pp. 5944–5967(2022)
[2] Huber, A., Kolmogorov, V.: Towards minimizing k-submodular functions. In: Mahjoub, A.R., Markakis, V., Milis, I. & Paschos V.T. (Eds.), Combinatorial optimization, Lecture notes in computer science, pp. 451–462. Springer, Heidelberg (2012)
[3] Iwata, S., Tanigawa, S., Yoshida, Y.: Improved approximation algorithms for k-submodular function maximization. In: Kraughgamer, R. (Eds.), Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404–413. Society for Industrial and Applied Mathematics (2016)
[4] Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and non-monotone submodular maximization with knapsack constraints. Math. Op. Res. 38(4), 729–739(2013)
[5] Li, J., Liu, Y.: Approximation algorithms for stochastic combinatorial optimization problems. J. Op. Res. Soc. China 4, 1–47(2016)
[6] Liu, Q., Yu, K., Li, M., Zhou, Y.: k-submodular maximization with a knapsack constraint and p matroid constraints. Tsinghua Sci. Technol. 28(5), 896–905(2023)
[7] Matsuoka,T.,Ohsaka,N.:Maximizationofmonotonek-submodularfunctionswithboundedcurvature and non-k-submodular functions. In: V. N. Balasubramanian, & I. Tsang (Eds.), Proceedings of the 13th Asian Conference on Machine Learning, pp. 1707–1722(2021)
[8] Nguyen, L., Thai, M.: Streaming k-submodular maximization under noise subject to size constraint. In: H. Daumé, & A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, pp. 7338–7347(2020)
[9] Ohsaka, N., Yoshida, Y.: Monotone k-submodular function maximization with size constraints. In: C. Cortes, N. Lawrence, D. Lee and M. Sugiyama, & R. Garnett (Eds.), Proceedings of the 29th Conference on Neural Information Processing Systems, pp. 694–702. Curran Associates, Inc. (2015)
[10] Oshima, H.: Improved randomized algorithm for k-submodular function maximization. SIAM J. Discr. Math. 35(1), 1–22(2021)
[11] Pham, C., Vu, Q., Ha, D., Nguyen, T., Le, N.: Maximizing k-submodular functions under budget constraint: applications and streaming algorithms. J. Comb. Optim. 44, 723–751(2022)
[12] Quoc, H., Tam, N., Nhan, T.: The continuous knapsack problem with capacities. J. Op. Res. Soc. China 9, 713–721(2021)
[13] Rafiey, A., Yoshida, Y.: Fast and private submodular and k-submodular functions maximization with matroid constraints. In: H. Daumé, & A. Singh (Eds), Proceedings of the 37th International Conference on Machine Learning, pp. 7887–7897(2020)
[14] Sakaue, S.: On maximizing a monotone k-submodular function subject to a matroid constraint. Discr. Optim. 23, 105–113(2017)
[15] Shi, G., Gu, S., Wu, W.: k-submodular maximization with two kinds of constraints. Discr. Math. Algorithms Appl. 13(4), 2150036(2021)
[16] Sun, Y., Liu, Y., Li, M.: Maximization of k-submodular function with a matroid constraint. In: Du, D., Du, D., Wu, C.,& Xu, D. (Eds.), Proceedings of the 17th Annual Conference on Theory and Applications of Models of Computation, pp. 1–10. Springer, Cham (2022)
[17] Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Op. Res. Lett. 32(1), 41–43(2004)
[18] Tang, Z., Wang, C., Chan, H.: On maximizing a monotone k-submodular function under a knapsack constraint. Op. Res. Lett. 50(1), 28–31(2022). https://doi.org/10.1016/j.orl.2021.11.010
[19] Tang,Z.,Wang,C.:Improvedanalysisofgreedyalgorithmonk-submodularknapsack.In:Proceedings of the 26th European Conference on Artificial Intelligence, pp.2338–2345(2023)
[20] Wang, B., Zhou, H.: Multilinear extension of k-submodular functions (2021). https://doi.org/10. 48550/arXiv.2107.07103
[21] Ward, J., Živný, S.: Maximizing k-submodular functions and beyond. ACM Trans. Algorithms 47, 1–26(2016)
[22] Wolsey, L.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Op. Res. 7(3), 410–425(1982)
[23] Xiao, H., Liu, Q., Zhou, Y., Li, M: Non-monotone k-submodular function maximization with individual size constraints. In: T. N. Dinh, & M. Li (Eds.), Proceedings of the 11th International Conference on Computational Data and Social Networks, pp. 268–279. Springer, Cham (2022)
[24] Yu, K., Li, M., Zhou, Y., Liu, Q.: On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints. J. Comb. Optim. 45, 93(2023)
[25] Zheng, L., Chan, H., Loukides, G., Li, M.: Maximizing approximately k-submodular functions. In: C. Demeniconi, I. Davidson, L. Akoglu, & E. Terzi (Eds.), Proceedings of the 2021 SIAM International Conference on Data Mining, pp.414–422. Society for Industrial and Applied Mathematics (2021)