AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.9 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window

School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, and also with Key Laboratory of Ministry of Education Numerical Simulation of Large Scale Complex Systems, Nanjing 210023, China
School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China
Faculty of Management, University of New Brunswick, Fredericton E3B9Y2, Canada
Show Author Information

Abstract

Submodular function maximization problem has been extensively studied recently. A natural variant of submodular function is k-submodular function, which has many applications in real life, such as influence maximization and sensor placement problem. The domain of a k-submodular function has k disjoint subsets, and hence includes submodular function as a special case when k=1. This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window. Based on the smooth histogram technique, we design a deterministic approximation algorithm. Furthermore, we propose a randomized algorithm to improve the approximation ratio.

Keywords

k-submodular functiond-knapsack constraintssliding windowstreaming algorithmapproximation algorithm

References

[1]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions—I, Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
Crossref Google Scholar
[2]

G. L. Nemhauser and L. A. Wolsey, Best algorithms for approximating the maximum of a submodular set function, Math. Oper. Res., vol. 3, no. 3, pp. 177–188, 1978.
Crossref Google Scholar
[3]
M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, An analysis of approximations for maximizing submodular set functions—II, in Mathematical Programming Studies. Berlin, Germany: Springer, 1978. pp. 73–87.
Crossref
[4]
U. Feige, A threshold of ln(n) for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
Crossref
[5]

M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., vol. 32, no. 1, pp. 41–43, 2004.
Crossref Google Scholar
[6]

G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM Journal on Computing, vol. 40, no. 6, pp. 1740–1766, 2011.
Crossref Google Scholar
[7]
A. Badanidiyuru and J. Vondrák, Fast algorithms for maximizing submodular functions, in Proc. Twenty-Fifth Annual ACM-SIAM Symp. on Discrete Algorithms, Philadelphia, PA, USA, 2014, pp. 1497−1514.
Crossref
[8]
N. Ohsaka and Y. Yoshida, Monotone k-submodular function maximization with size constraints, in Proc. 28th Int. Conf. Neural Information Processing Systems − Volume 1, Montreal, Canada, 2015, pp. 694–702.
[9]
Z.-H. Zhou, Y. Yu, and C. Qian, Evolutionary Learning : Advances in Theories and Algorithms. Singapore: Springer, 2019.
Crossref
[10]

C. Qian, J.-C. Shi, K. Tang, and Z.-H. Zhou, Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee, IEEE Trans. Evol. Comput., vol. 22, no. 4, pp. 595–608, 2018.
Crossref Google Scholar
[11]
A. Singh, A. Guillory, and J. Bilmes, On bisubmodular maximization, in Proc. of Artificial Intelligence and Statistics, Palau de Congressos, Spain, 2012, pp. 1055−1063.
[12]

J. Ward and S. Živný, Maximizing k-submodular functions and beyond, ACM Trans. Algorithms, vol. 12, no. 4, pp. 1–26, 2016.
Crossref Google Scholar
[13]
S. Iwata, S. Tanigawa, and Y. Yoshida, Improved approximation algorithms for k-submodular function maximization in Proc. of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA, 2016, pp. 404−413.
Crossref
[14]

H. Oshima, Improved randomized algorithm for k-submodular function maximization, SIAM J. Discrete Math., vol. 35, no. 1, pp. 1–22, 2021.
Crossref Google Scholar
[15]

S. Sakaue, On maximizing a monotone k-submodular function subject to a matroid constraint, Discrete Optim., vol. 23, pp. 105–113, 2017.
Crossref Google Scholar
[16]

Z. Tang, C. Wang, and H. Chan, On maximizing a monotone k-submodular function under a knapsack constraint, Oper. Res. Lett., vol. 50, no. 1, pp. 28–31, 2022.
Crossref Google Scholar
[17]
B. Wang and H. Zhou, Multilinear extension of k-submodular functions, arXiv preprint arXiv: 2107.07103, 2021.
[18]
A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, Streaming submodular maximization: Massive data summarization on the fly, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 671–680.
Crossref
[19]

C.-C. Huang, N. Kakimura, and Y. Yoshida, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Algorithmica, vol. 82, no. 4, pp. 1006–1032, 2020.
Crossref Google Scholar
[20]

C.-C. Huang and N. Kakimura, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Algorithmica, vol. 83, no. 3, pp. 879–902, 2021.
Crossref Google Scholar
[21]

Q. Yu, L. Xu, and S. Cui, Streaming algorithms for news and scientific literature recommendation: Monotone submodular maximization with a Knapsack constraint, IEEE Access, vol. 6, pp. 53736–53747, 2018.
Crossref Google Scholar
[22]
C. Chekuri, S. Gupta, and K. Quanrud, Streaming algorithms for submodular function maximization, in Automata, Languages, and Programming. Berlin, Germany: Springer, 2015. pp. 318–330.
Crossref
[23]

R. Kumar, B. Moseley, S. Vassilvitskii, and A. Vattani, Fast greedy algorithms in MapReduce and streaming, ACM Trans. Parallel Comput., vol. 2, no. 3, pp. 1–22, 2015.
Crossref Google Scholar
[24]

C. V. Pham, Q. C. Vu, D. K. T. Ha, T. T. Nguyen, and N. D. Le, Maximizing k-submodular functions under budget constraint: Applications and streaming algorithms, J. Comb. Optim., vol. 44, no. 1, pp. 723–751, 2022.
Crossref Google Scholar
[25]
A. Epasto, S. Lattanzi, S. Vassilvitskii, and M. Zadimoghaddam, Submodular optimization over sliding windows, in Proc. 26th Int. Conf. World Wide Web, Perth, Australia, 2017, pp. 421–430.
Crossref
[26]
V. Braverman and R. Ostrovsky, Smooth histograms for sliding windows, in Proc. 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS'07), Providence, RI, USA, 2007, pp. 283–293.
Crossref
[27]

Y. Wang, Y. Li, and K.-L. Tan, Efficient representative subset selection over sliding windows, IEEE Trans. Knowl. Data Eng., vol. 31, no. 7, pp. 1327–1340, 2019.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 30 Issue 2,
April 2025
Pages 488-498
DOI: 10.26599/TST.2023.9010121
Cite this article:
Wang W, Sun Y, Sun Z, et al. Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window. Tsinghua Science and Technology, 2025, 30(2): 488-498. https://doi.org/10.26599/TST.2023.9010121

95

Views

27

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 07 July 2023
Revised: 23 August 2023
Accepted: 10 October 2023
Published: 09 December 2024
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return