Approximation algorithms for k-submodular maximization subject to a knapsack constraint

In this paper, we study the problem of maximizing k-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a frac12(1-e-2)≈ 0.432 greedy approximation algorithm. For the non-monotone case, we are the first to consider the knapsack problem and provide a greedy-type combinatorial algorithm with approximation ratio frac13(1-e-3)≈ 0.317.