k-Submodular maximization with two kinds of constraints

k-submodular maximization is a generalization of submodular maximization, which requires us to select k disjoint subsets instead of one subset. Attracted by practical values and applications, we consider k-submodular maximization with two kinds of constraints. For total size and individual size difference constraints, we present a (1 - e(-1/k) - epsilon)-approximation algorithm for maximizing a nonnegative k-submodular function, running in time O(n(k-1)!/epsilon log n/epsilon + k(k - 1)) at worst. Specially, if B is multiple of k, the approximation ratio can reduce to (1 - e(-1/k-1) - epsilon), running in time O(n(k-1)!/epsilon log n/epsilon) at worst. Besides, this algorithm can be applied to alpha-bisubmodular achieving (1 - 1/root e - epsilon)-approximation running in time O(n/epsilon log n/epsilon + 2). Furthermore, if B is multiple of 2, the approximation ratio can reduce to (1 - 1/e - epsilon), running in time O(n/epsilon log n/epsilon) at worst. For individual size constraint, there is a (1 - 1/e - epsilon)-approximation algorithm for maximizing a nonnegative k-submodular function and an nonnegative alpha-bisubmodular function, running in time O(nk!/epsilon log n/epsilon) and O(2n/epsilon log n/epsilon), respectively, at worst.

Automated summary

The article discusses approximation algorithms for k-submodular maximization problem under two types of constraints, providing corresponding time complexity and approximation ratio.