Background

设 是大小为 的有限集. 一个实值函数 被称为次模函数 iff 对任意 的子集 都成立. 称为一个次模系统. 若 对任意 都成立, 则称 是对称次模函数. 对于任意次模函数 , 它的对称部分定义为 是由一个 function value oracle 给出的, 这个 oracle 可以对任意输入的集合 输出 的数值. 会特别强调一个算法中对 -value oracle 调用的次数, 这会直接作为时间复杂度.

这篇文章的内容如下:

• 定义 pendent pairs, 并给出一个需要 次 -value oracle calls 的算法求出一个次模系统 的 pendent pairs
• 用 pendent pairs 找到 的对称部分的 的一个非平凡 minimizer. It also uses the fact that it is easy to enforce, for symmetric submodular functions, the requirement that an optimum set must not separate any two given elements of .

Pendent pairs

的一个 pendent pairs 是序偶 , 满足

• .

若 满足 且 , 则称 separate from .

pendent pairs 的存在性和对称次模函数的 cut-equivalent 的存在性是一致的.

算法构造 上的一个序列 ,

Using pendent pairs for finding an optimum set

Related problems