k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints  

作　　者：Qian Liu Kemin Yu Min Li Yang Zhou 

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

出　　处：《Tsinghua Science and Technology》2023年第5期896-905,共10页清华大学学报（自然科学版（英文版）

基　　金：supported by the Natural Science Foundation of Shandong Province of China(Nos.ZR2020MA029,ZR2021MA100);the National Natural Science Foundation of China(No.12001335).

摘　　要：A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

关 键 词：k-submodularity knapsack constraint matroid constraint approximation algorithm 

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