Improved approximation algorithms for k-submodular function maximization

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)}-approximation by Ward and Zivný [18], where a = max{1, [EQUATION]}. We also show that for monotone k-submodular functions there is ... View More