Maximizing k-Submodular Functions and Beyond

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k≥ 2 and 1≤ r≤ k. We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+r). For r=k, we give an analysis of a randomised greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+√k/2). In the case of k=r=2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that NPneq RP. Extending a result of Ando et al., we show that for any k≥ 3 submodularity in every orthant and pairwise monotonicity (i.e. r=2) precisely characterize k-submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k) for the maximization problem of k-submodular functions.