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
PDF (1.4 MB)
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.

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

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

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

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

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

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

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

[14]
J. Ward, Oblivious and non-oblivious local search for combinatorial optimization, PhD thesis, University of Toronto, Canada, 2012.
Tsinghua Science and Technology
Pages 1703-1708
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

120

Views

10

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