收录:
摘要:
In this work, we investigate the problem that maximizes a weakly k-submodular function under the matroid constraint. Different from traditional submodular function maximization, there are k disjoint subsets in k-submodular function optimization, instead of a single set in the submodular maximization. For the weakly k-submodular maximization problem, we provide a greedy algorithm whose approximation ratio is alpha/(1 + alpha), where parameter 0 < alpha <= 1 is the orthant submodularity ratio. Then we extend to cardinality constraint which maintains the same performance ratio.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022
ISSN: 0302-9743
年份: 2022
卷: 13571
页码: 393-401
归属院系: