@article{Liu2024, 
author = {Yuezhu Liu and Yunjing Sun and Min Li},
title = {Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint},
year = {2024},
journal = {Tsinghua Science and Technology},
volume = {29},
number = {6},
pages = {1633-1641},
keywords = {matroid constraint, streaming algorithm, k-submodular, deterministic algorithm, randomized algorithm},
url = {https://www.sciopen.com/article/10.26599/TST.2023.9010122},
doi = {10.26599/TST.2023.9010122},
abstract = {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.}
}