Improved Approximation Algorithms for k-Submodular Function Maximization
Improved Approximation Algorithms for k-Submodular Function Maximization
复制标题
k-子模函数最大化的改进近似算法
DOI：
10.1137/1.9781611974331.ch30
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
and Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Satoru Iwata;Shin-ichi Tanigawa;and Yuichi Yoshida
提出了一种求非负k次模函数最大值的多项式时间1/2逼近算法。这改进了之前Ward和Živný[18]的max{1/3, 1/(1 +a)}近似，其中a=。我们还证明了对于单调多项式次模函数存在一个多项式-timek/(2k - 1)近似算法，而对于任何一个最大化单调多项式次模函数的一个（(k+ 1)/2k+）近似算法将需要指数级的查询。特别是，我们的硬度结果表明我们的算法是渐近紧密的。我们还扩展了该方法，以提供用于最大化skewbisu模函数的常因子逼近算法，这些算法最近作为双模函数的推广而引入。
This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegativek-submodular functions. This improves upon the previous max{1/3, 1/(1 +a)}-approximation by Ward and Živný [18], wherea= . We also show that for monotonek-submodular functions there is a polynomial-timek/(2k– 1)-approximation algorithm while for any∊> 0 a ((k+ 1)/2k+∊)-approximation algorithm for maximizing monotonek-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.