SUBMODULAR SET-FUNCTIONS, MATROIDS AND THE GREEDY ALGORITHM - TIGHT WORST-CASE BOUNDS AND SOME GENERALIZATIONS OF THE RADO-EDMONDS THEOREM
SUBMODULAR SET-FUNCTIONS, MATROIDS AND THE GREEDY ALGORITHM - TIGHT WORST-CASE BOUNDS AND SOME GENERALIZATIONS OF THE RADO-EDMONDS THEOREM
复制标题
DOI：
10.1016/0166-218x(84)90003-9
复制
发表时间：
1984-01-01
影响因子：
1.1
通讯作者：
CORNUEJOLS, G
中科院分区：
文献类型：
--
作者：
CONFORTI, M;CORNUEJOLS, G
对于问题maxlcub; Z（S）：S是拟阵Xrcub;中的独立集，众所周知，当Z是可加集函数时，贪婪算法找到最优解（Rado-Edmonds定理）。Fisher、Nemhauser和Wolsey证明了，当Z是满足Z（n）= 0的非减次模集函数时，贪婪算法找到的解的值至少是最优值的一半。本文证明了它能找到一个值至少是最优值的1/（1+ α）倍的解，其中α是表示Z的“全曲率”的参数。这个参数满足0≤ α≤ 1和α= 0当且仅当集合函数Z是可加的。因此Rado-Edmonds定理和Fisher-Nemhauser-Wolsey定理都包含在1/（1+ α）界中。我们证明了这个界在α方面是最好的。另一个界限，推广了Rado-Edmonds定理，给出了一个“贪婪曲率”的集合函数。与第一个界限不同，这个界限可以证明贪婪算法的最优性，即使在Z不是可加性的情况下。第三个界，在秩和围长方面的X，统一和推广已知的界限（e-1）/e一致拟阵和1 2一般拟阵。我们还分析了贪婪算法的性能时，X是一个独立的系统，而不是一个拟阵。然后我们得到了两个紧界：第一个是[1−（1− α/K）k]/α，其中K和k分别是X中最大和最小的极大独立集的大小;第二个是1/（p+ α），其中p是获得X所需的拟阵的最小个数。
For the problem maxlcub; Z (S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z (∅)= 0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1+ α) times the optimum value, where α is a parameter which represents the ‘total curvature’of Z. This parameter satisfies 0≤ α≤ 1 and α= 0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1+ α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e− 1)/e known for uniform matroids and 1 2 for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1−(1− α/K) k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+ α) where p is the minimum number of matroids that must be intersected to obtain X.