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 Živný [18], where a =. We also show that for monotone k -submodular functions there is a polynomial-time k /(2 k – 1)-approximation algorithm while for any ∊ > 0 a (( k + 1)/2 k + ∊ )-approximation algorithm for maximizing monotone k -submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

Authors

• Satoru Iwata 0001
• Shin-ichi Tanigawa
• Yuichi Yoshida

Keywords

No keywords are indexed for this paper.