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 \(\frac{1}{2}(1-\textrm{e}^{-2})\approx 0.432\) $\frac{1}{2}(1-{\text{e}}^{-2})\approx 0.432$ greedy approximation algorithm, improving the previous best-known ratio \(\frac{1}{2}(1-\textrm{e}^{-1})\approx 0.316\) $\frac{1}{2}(1-{\text{e}}^{-1})\approx 0.316$ . We also consider the non-monotone knapsack problem and provide two algorithms. The first is a greedy-type combinatorial algorithm with approximation ratio \(\frac{1}{3}(1-\textrm{e}^{-3})\approx 0.317\) $\frac{1}{3}(1-{\text{e}}^{-3})\approx 0.317$ , while the second is a multilinear-extension-based algorithm with approximation ratio \(\frac{1}{3}-\varepsilon \) $\frac{1}{3}-\epsilon$ , where \(\varepsilon >0\) $\epsilon >0$ .