Multilinear extension of $k$-submodular functions

A $k$-submodular function is a pairwise monotone function that given $k$ disjoint subsets outputs a value that is submodular in every orthant. In this paper, we provide a new framework for $k$-submodular maximization problems, by relaxing the optimization to the continuous space with the multilinear extension of $k$-submodular functions and rounding the fractional solution to recover the discrete solution. The multilinear extension introduces new techniques to analyze and optimize $k$-submodular functions. When the variables are unconstrained, we propose simple algorithms that achieve almost $\frac{1}{2}$-approximation, which is asymptotically optimal. For finite $k$, the factors could be improved to almost as good as any combinatorial algorithm based on Iwata, Tanigawa, and Yoshida's meta-framework ($\frac{k}{2k-1}$-approximation for the monotone case and $\frac{k^2+1}{2k^2+1}$-approximation for the non-monotone case). For monotone functions, almost $\frac{1}{2}$-approximation are obtained under total size and knapsack constraints.