Title: Improved approximation algorithms for k-submodular function maximization
Abstract: 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 a polynomial-time k/(2k --1)-approximation algorithm while for any e > 0 a ((k + 1)/2k + e)-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.
Publication Year: 2016
Publication Date: 2016-01-10
Language: en
Type: article
Access and Citation
Cited By Count: 22
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot