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

[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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Rui Guan, Dong-Yue Liang, Wei Wang, Wei-Hua Yang. Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem [J]. Journal of the Operations Research Society of China, 2026, 14(2): 719-729.
[2]	Zhen Zhang, Zi-Yun Huang, Zhi-Ping Tian, Li-Mei Liu, Xue-Song Xu, Qi-Long Feng. On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces [J]. Journal of the Operations Research Society of China, 2026, 14(1): 309-324.
[3]	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.
[4]	Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li. Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints [J]. Journal of the Operations Research Society of China, 2025, 13(2): 535-554.
[5]	Pei-Jia Yang, Wen-Chang Luo. Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2025, 13(1): 287-296.
[6]	Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[7]	Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang. Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem [J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.
[8]	Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang. Local search yields a PTAS for fixed-dimensional k-means problem with penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 351-362.
[9]	Wen-Zhao Liu, Min Li. An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 387-409.
[10]	Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang. Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions [J]. Journal of the Operations Research Society of China, 2024, 12(2): 428-445.
[11]	Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou. An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 495-504.
[12]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[13]	Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang. The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor [J]. Journal of the Operations Research Society of China, 2023, 11(4): 735-758.
[14]	Jin-Shuang Guo, Wen Liu, Bo Hou. An Approximation Algorithm for P-prize-collecting Set Cover Problem [J]. Journal of the Operations Research Society of China, 2023, 11(1): 207-218.
[15]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.