Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint  

作　　者：Yuezhu Liu Yunjing Sun Min Li 

机构地区：[1]School of Mathematics and Statistics,Shandong Normal University,Jinan 250014,China

出　　处：《Tsinghua Science and Technology》2024年第6期1633-1641,共9页清华大学学报自然科学版（英文版）

基　　金：supported by the Natural Science Foundation of Shandong Province of China(No.ZR2020MA029).

摘　　要：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.

关 键 词：k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm 

分 类 号：O174[理学—数学]