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

05/31/2021

∙

by   Zhongzheng Tang, et al.

∙

0

∙

share

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 (1/2-1/2e)-approximation algorithm that evaluates f O(n^5k^4) times.