Efficient Algorithms for k-Submodular Function Maximization with p-System and d-Knapsack Constraint

The k-submodular function is a generalization of the submodular function. The k-submodular optimization problems have important applications in influence maximization problems and sensor placement problems with k kinds of sensors. In this paper, we study the problems of maximizing k-submodular functions subject to two kinds of constraints. We set \(\alpha =2\) when f is monotone and \(\alpha =3\) when f is non-monotone. For the p-system constraint, we get a \(\frac{1-\epsilon }{p+\alpha }\) -approximation ratio. For the intersection of p-system and d-knapsack constraints, we get an approximation ratio of \(\frac{1-\epsilon }{p+\alpha +2d}\) . And subsequently, we propose an improved algorithm that improves the approximation ratio to \(\frac{1-\epsilon }{p+\alpha +\frac{1+\sqrt{5}}{2}d}\) .