On maximizing a monotone $k$-submodular function under a knapsack constraint

We study the problem of maximizing a monotone $k$-submodular function $f$ under a knapsack constraint, where a $k$-submodular function is a natural generalization of a submodular function to $k$ dimensions. We present a deterministic $(\frac12-\frac{1}{2e})$-approximation algorithm that evaluates $f$ $O(n^5k^4)$ times.