Greedy+Max: An Efficient Approximation Algorithm for k-Submodular Knapsack Maximization

This paper studies the problem of maximizing a k-submodular function under a knapsack constraint. A k-submodular function is a generalization of submodular functions, which takes k disjoint subsets of elements as input and outputs a real value. Many problems in combinatorial optimization and machine leaning can be modeled as k-submodular maximization problems, such as influence maximization, sensor placement, feature selection, etc. In this paper, we propose a novel greedy-based algorithm, called Greedy+Max, which augments every partial greedy solution by a feasible item with maximum marginal gain, and returns the best augmented solution. We prove that it achieves a \(\frac{1}{3}\) -approximation for monotone functions and a \(\frac{1}{4}\) -approximation for non-monotone functions, with a low query complexity.