Maximizing k-Submodular Functions and Beyond

Abstract

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\ge 2$ and $1\le r\le 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+\sqrt{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 $NP\ne RP$. Extending a result of Ando et al., we show that for any $k\ge 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.

Full version of a SODA'14 paper, to appear in ACM Transactions on Algorithms (TALG)

Cited by in corpus (7)

• On k-Submodular Relaxation
• Improved randomized algorithm for $k$-submodular function maximization
• On Optimal Approximations for $k$-Submodular Maximization via Multilinear Extension
• On maximizing a monotone k-submodular function subject to a matroid constraint
• An Exact Cutting Plane Method for $k$-submodular Function Maximization
• Sensitivity Analysis of Submodular Function Maximization
• Derandomization for k-submodular maximization