Publications
Sort:
Open Access Issue
k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints
Tsinghua Science and Technology 2023, 28 (5): 896-905
Published: 19 May 2023
Downloads:89

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.

total 1