Improved Approximation Algorithms for k-Submodular Function Maximization

Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max \{1/3,1/(1+a)\}$-appr…