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
Discover the SciOpen Platform and Achieve Your Research Goals with Ease.
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
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.
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.
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.
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.
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.
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.
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.
274
Views
32
Downloads
0
Crossref
0
Web of Science
0
Scopus
0
CSCD
Altmetrics
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/).