TY - JOUR
AU - Liu, Yuezhu
AU - Sun, Yunjing
AU - Li, Min
PY - 2024
TI - Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint
JO - Tsinghua Science and Technology
SN - 1007-0214
SP - 1633
EP - 1641
VL - 29
IS - 6
AB - In this paper, we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint. In order to reduce the complexity of this algorithm, we also present a randomized 1/3-approximation algorithm with the probability of 1−ε, where ε is the probability of algorithm failure. Moreover, we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.
UR - https://doi.org/10.26599/TST.2023.9010122
DO - 10.26599/TST.2023.9010122