集合覆盖问题的近似算法

1.   集合覆盖问题

集合覆盖问题是一个最优化问题，其原型是多资源选择问题。集合覆盖问题可以看作是图的顶点覆盖问题的推广，因此也是一个NP难问题。

给定一个有n个元素的集合，U的一个子集的集合为，目标是找到一个子集能够覆盖U的所有元素。测量函数为计算选择子集的总成本

          

算法实现为：

   

一个集合S的成本有效性是指它覆盖新元素时的平均成本，一个元素e的成本是当e被覆盖时的平均成本。贪心集合覆盖的时间复杂度为O（mn）。

贪心集合覆盖时一个对于最小集合覆盖问题的Hn因子近似算法，其中即调和数。（Log-APX）

            

       最优覆盖的成本为1+ε，当贪心算法将输出覆盖的成本为

 参考：https://blog.csdn.net/ying_xu/article/details/51557363