$k$-Submodular Maximization with a Knapsack Constraint and $p$ Matroid Constraints
Qian Liu, Kemin Yu, Min Li, Yang Zhou · Tsinghua Science & Technology · 2023
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.