ANALYSIS OF APPROXIMATIONS FOR MAXIMIZING SUBMODULAR SET FUNCTIONS .2.
ANALYSIS OF APPROXIMATIONS FOR MAXIMIZING SUBMODULAR SET FUNCTIONS .2.
复制标题
DOI：
10.1007/bfb0121195
复制
发表时间：
1978-01-01
期刊：
影响因子：
--
通讯作者：
WOLSEY, LA
中科院分区：
文献类型：
--
作者：
FISHER, ML;NEMHAUSER, GL;WOLSEY, LA
设 N 是一个有限集和 N 的子集的非空集合，其具有 andF2⊂F1 隐含的属性。定义在 N 的子集上的实值函数 z，对于所有 S⊂T⊃，满足 z(S)≤z(T) -Nandz(S)+z(T)≥(S∪T)+z(S∩T)，对于所有 S，T⊂-Ni 称为非减子模。我们考虑问题，z(S)子模和非递减}以及它的几个特殊情况。我们分析贪婪和局部改进启发式，以及当z(S)是线性时的线性规划松弛。我们的结果是近似质量的最坏情况界限。例如，当 (N, ) 由 P 矩阵的交集来描述时，我们表明贪婪启发式总是产生一个值至少为最优值 1/(P+1) 倍的解决方案。对于所有正整数 P 都可以实现此界限。
LetNbe a finite set and a nonempty collection of subsets ofNwhich have the property that andF2⊂F1imply . A real-valued functionzdefined on the subsets ofNthat satifiesz(S)≤z(T)for allS⊂T⊃-Nandz(S)+z(T)≥(S∪T)+z(S∩T)for allS,T⊂-Nis called nondecreasing and submodular. We consider the problem ,z(S)submodular and nondecreasing} and several special cases of it.We analyze greedy and local improvement heuristics, and a linera programming relaxation whenz(S)is linear. Our results are worst case bounds on the quality of the approximations. For example, when (N, ) is described by the intersection ofPmatroids, we show that a greedy heuristic always produces a solution whose value is at least 1/(P+1) times the optimal value. This bound can be achieved for all positive integersP.