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 randomized greedy algorithm that shows that any such function can be approximated to a factor of 1/(1 + root 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 both in the value query model and under the assumption that NP not equal 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.