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.4 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

Two-Stage Submodular Maximization Under Knapsack Problem

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
College of Taizhou, Nanjing Normal University, Taizhou 225300, China
Faculty of Management, University of New Brunswick, Fredericton, E3B 5A3, Canada
School of Mathematical Science, Institute of Mathematics, and Ministry of Education Key Laboratory of NSLSCS, Nanjing Normal University, Nanjing 210023, China
Show Author Information

Abstract

Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization. In this paper, we consider knapsack constraint. In this problem, we give n articles and m categories, and the goal is to select a subset of articles that can maximize the function F(S). Function F(S) consists of m monotone submodular functions fj, j=1,2,…,m, and each fj measures the similarity of each article in category j. We present a constant-approximation algorithm for this problem.

Keywords

submodular functionknapsack constraintmatroid

References

[1]
Z. Liu, J. Jin, D. Du, and X. Zhang,Two-stage submodular maximization under knapsack and matroid constraints,in Proc. of 17th Annual Conf. on Theory and Applications of Models of Computation (TAMC),Tianjin, China, pp.140-154, 2022.
Crossref
[2]
E. Balkanski, B. Mirzasoleiman, A. Krause, and Y. Singer, Learning sparse combinatorial representations via two-stage submodular maximization, in Proc. of The 33rd Int. Conf. on Machine Learning, New York, NY, USA, pp. 2207−2216, 2016.
[3]
M. Mitrovic, E. Kazemi, M. Zadimoghaddam, and A. Karbasi, Data summarization at scale: A two-stage submodular approach, arXiv preprint arXiv: 1806.02815, 2018.
[4]
S. Stan, M. Zadimoghaddam, A. Krause, and A. Karbasi, Probabilistic submodular maximization in sub-linear time, in Proc. of the 34th Int. Conf. on Machine Learning, Sydney, Australia, 2017, pp. 3241−3250.
[5]

R. Yang, S. Gu, C. Gao, W. Wu, H. Wang, and D. Xu, A constrained two-stage submodular maximization, Theor. Comput. Sci., vol. 853, pp. 57–64, 2021.
Crossref Google Scholar
[6]

S. Gong, Q. Nong, W. Liu, and Q. Fang, Parametric monotone function maximization with matroid constraints, J. Glob. Optim., vol. 75, no. 3, pp. 833–849, 2019.
Crossref Google Scholar
[7]
R. Yang, D. Xu, L. Guo, and D. Zhang, Parametric streaming two-stage submodular maximization, in Lecture Notes in Computer Science, G. Goos and J. Hartmanis, eds. Cham, Switzerland: Springer International Publishing, pp. 193–204.
Crossref
[8]

Y. Li, Z. Liu, C. Xu, P. Li, X. Zhang, and H. Chang, Two-stage submodular maximization under curvature, J. Comb. Optim., vol. 45, no. 2, p. 77, 2023.
Crossref Google Scholar
[9]

M. Conforti and G. Cornuéjols, Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math., vol. 7, no. 3, pp. 251–274, 1984.
Crossref Google Scholar
[10]

M. Sviridenko, J. Vondrák, and J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, Math. Oper. Res., vol. 42, no. 4, pp. 1197–1218, 2017.
Crossref Google Scholar
[11]

Y. Yoshida, Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint, SIAM J. Discrete Math., vol. 33, no. 3, pp. 1452–1471, 2019.
Crossref Google Scholar
[12]
Z. Liu, H. Chang, R. Ma, D. Du, and X. Zhang, Two-stage submodular maximization problem beyond non-negative and monotone, Lecture Notes in Computer Science. Cham Switzerland: Springer International Publishing, 2020, pp. 144–155.
Crossref
[13]

J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko, Maximizing nonmonotone submodular functions under matroid or knapsack constraints, SIAM J. Discrete Math., vol. 23, no. 4, pp. 2053–2078, 2010.
Crossref Google Scholar
[14]
J. Ward, Oblivious and non-oblivious local search for combinatorial optimization, PhD thesis, University of Toronto, Canada, 2012.
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1703-1708
DOI: 10.26599/TST.2023.9010107
Cite this article:
Liu Z, Jin J, Du D, et al. Two-Stage Submodular Maximization Under Knapsack Problem. Tsinghua Science and Technology, 2024, 29(6): 1703-1708. https://doi.org/10.26599/TST.2023.9010107

275

Views

32

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 15 December 2022
Revised: 08 March 2023
Accepted: 17 September 2023
Published: 20 June 2024
© The Author(s) 2024.

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