Maximizing k-Submodular Functions and Beyond
Maximizing k-Submodular Functions and Beyond
复制标题
最大化 k 子模函数及其他函数
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Stanislav Živný
中科院分区：
文献类型：
--
作者：
Justin Ward;Stanislav Živný
我们考虑在每个正交和r向单调的次模集合的k元组上定义的函数的值oracle模型中的最大化问题，其中k大于或等于2和1≤r≤k。我们给出确定性贪婪算法的分析，该算法表明任何此类函数可以近似为1/(1 + r)的因子。对于r = k，我们给出了一个随机贪婪算法的分析，该算法表明任何这样的函数都可以近似为1/(1+√k/2)的因子。在k = r = 2的情况下，所考虑的函数精确地对应于双次模函数，在这种情况下，我们得到了1/2的近似保证。我们证明，在子模函数的情况下，无论在值查询模型中还是在NP≠RP的假设下，这个结果都是最好的。扩展Ando等人的结果，我们表明，对于任何k小于3，每个正交中的子模块性和成对单调性（即r = 2）精确地表征k-子模块函数。因此，对于k次模函数的最大化问题，我们得到了1/3的近似保证（因此与k无关）。
We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k ⩾ 2 and 1 ⩽ r ⩽ k. We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1 + r). For r = k, we give an analysis of a randomized greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+√k/2. In the case of k = r = 2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible both in the value query model and under the assumption that NP ≠ RP. Extending a result of Ando et al., we show that for any k ⩾ 3, submodularity in every orthant and pairwise monotonicity (i.e., r = 2) precisely characterize k-submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k) for the maximization problem of k-submodular functions.
偏斜双子模性和有价值的 CSP
影响因子：
1.6
作者：
Huber A
通讯作者：
Huber A