期刊
TSINGHUA SCIENCE AND TECHNOLOGY
卷 28, 期 5, 页码 896-905出版社
TSINGHUA UNIV PRESS
DOI: 10.26599/TST.2022.9010039
关键词
k-submodularity; knapsack constraint; matroid constraint; approximation algorithm
A k-submodular function is a generalization of a submodular function that allows for k disjoint subsets instead of single subsets. The problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints has been addressed in this paper with a proposed nested greedy and local search algorithm.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据