lecture-集合覆盖近似算法.ppt

集合覆盖近似算法 高文宇 gwyy@163.com 集合覆盖问题 许多问题如点覆盖，支配集等都是集合覆盖问题的特例。 集合覆盖问题 Set-Cover 下图中，F={S1, S2, S3, S4, S5, S6}，一个最小的集合覆盖为C={S3, S4, S5}。可用矩阵表示每个子集能覆盖的元素个数。 Greedy-Set-Cover近似算法 在每一阶段都选出能覆盖最多的，未被覆盖的元素的集合S。 GSC的近似度 Theorem 35.4 GREEDY-SET-COVER 是一个多项式时间的ρ(n)-近似算法，其中 Corollary 35.5 GREEDY-SET-COVER是一个多项式时间的 (ln |X|+ 1)-近似算法。 集合覆盖近似度的证明（1） 证明： （1）为了证明其是一个ρ(n)-近似算法，对每一个由该算法选出的集合赋予一个代价1，将这一代价平分到初次被覆盖的元素上，在利用这些代价来导出一个最优集合覆盖C*的规模和由该算法得到的集合覆盖C的规模之间的关系。 集合覆盖近似度的证明（2.1） （2）设Si表示由GSC算法所选出的第i个子集；在将Si加入C时要产生代价1。将这个选择Si的代价平均分布于首次被Si覆盖的元素之上。设cx表示分配给元素x的代价，x∈X。对每一个元素只分配一次代价，即当它首次被覆盖时分配一个代价。如果x首次被Si覆盖，则有： 集合覆盖近似度的证明（2.2） 一个计算cx的示例。例如按顺序选择S1、S2、S3，则分配给a、e、f、h的代价分别为1/4，分配给b、d、g的代价为1/3，分配给c的代价为1。总代价∑cx为3。若按其它顺序选择不同集合（如最优解的某个顺序），则cx可能会重复，因此这种选择下的∑cx一定大于等于3。 集合覆盖近似度的证明（3） （3）在算法的每一步中，要产生1个代价，因此有： 分配给最优覆盖的代价为： 由于每一个x∈X都至少在一个集合S∈C*中，因此有： 将上面的两个不等式组合起来，有： 集合覆盖近似度的证明（4） （4）证明的余下部分关键在于以下的不等式，稍后再对其进行证明。对属于F的任何集合S，有： 根据前面的式子可得： 集合覆盖近似度的证明（5） （5）考虑任意集合S∈F，和i = 1, 2, ..., |C|。设：ui = |S - (S1∪S2 ∪···∪Si)|为 贪心集合覆盖算法选择 S1, S2, ..., Si 后， S中仍未被覆盖的元素的个数。 定义 u0 = |S| 为S中元素的个数。设k 为使uk = 0的最小下标，因此S 中的每一个元素至少被S1, S2, ..., Sk中的某一个所覆盖。对于i = 1, 2, ..., k，有 ui-1 ≥ ui，并且S中共有ui-1 - ui 个元素首次被Si所覆盖。于是有： 注意到|Si - (S1∪S2∪···∪Si-1)|≥ |S - (S1∪S2∪···∪Si-1)|?=ui-1, 因为贪心算法中对 Si 的选择保证了Si比任意集合 S 覆盖更多的元素。由此可得： 集合覆盖近似度的证明（6） （6）由前式可得： 集合覆盖近似度的证明（7） Corollary 35.5 GREEDY-SET-COVER is a polynomial-time (ln |X|+ 1)-approximation algorithm. Proof Use inequality (A.14) and Theorem 35.4. 集合覆盖近似算法思考题 Exercises 35.3-4 Show that the following weaker form of Theorem 35.4 is trivially true: 集合覆盖的应用 求连通支配集 （1）用GSC算法求得一个支配集的近似最优解DS，近似度为(ln |X|+ 1)。 （2）利用Steiner Tree算法将前面所得的近似最优解DS连成一个连通的点集，即得到一个较好的连通支配集CDS。 再见 再见 * *