On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints

摘要

A k-submodular function is a generalization of a submodular function. The definition domain of a k-submodular function is a collection of k-disjoint subsets instead of simple subsets of ground set. In this paper, we consider the maximization of a ksubmodular function with the intersection of a knapsack and m matroid constraints. When the k-submodular function is monotone, we use a special analytical method to get an approximation ratio m/1+2 (1 -e(-(m+2))) for a nested greedy and local search algorithm. For non-monotone case, we can obtain an approximate ratio 1/m+3 (1 - e(-(m+3))).