Abstract
In this paper, we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone
Discover the SciOpen Platform and Achieve Your Research Goals with Ease.
In this paper, we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., vol. 40, no. 6, pp. 1740–1766, 2011.
J. Ward and S. Živný, Maximizing k-submodular functions and beyond, ACM Trans. Algorithms, vol. 12, no. 4, pp. 1–26, 2016.
H. Oshima, Improved randomized algorithm for k-submodular function maximization, SIAM J. Discrete Math., vol. 35, no. 1, pp. 1–22, 2021.
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.
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., vol. 40, no. 6, pp. 1740–1766, 2011.
S. Fujishige and S. Iwata, Bisubmodular function minimization, SIAM J. Discrete Math., vol. 19, no. 4, pp. 1065–1073, 2005.
Z. Tang, C. Wang, and H. Chan, Monotone k-submodular secretary problems: Cardinality and knapsack constraints, Theor. Comput. Sci., vol. 921, pp. 86–99, 2022.
475
Views
149
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/).