Improved randomized algorithm for k-submodular function maximization

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata et al. gave randomized k/(2k-1)-approximation algorithm for monotone functions, and randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives frack2+12k2+1-approximation for k≥ 3. We also give a randomized frac√17-32-approximation algorithm for k=3. We use the same framework used in Iwata et al. and Ward and vZivn'y with different probabilities.