集盖的近似值
我开始学习近似算法， 我正在读一本关于这方面的书，但我不明白对集合覆盖算法的分析。
有人可以解释一下引理2.3吗？ 它很短，但我不明白...
I started learning about approximation algorithms,
I'm reading a book about that and I don't understand the analysis for the set cover algorithm.
Can someone please explain lemma 2.3 ?
it's short but I don't understand it...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该算法为宇宙
U的每个元素分配一个“价格”price(e)，其中该价格是集合S的成本用于覆盖e除以集合S新覆盖的元素数量（由于定义，任何已经覆盖的元素必须被先前的集合分配较低的价格算法）。存在一个最优解，它选择一组总成本
OPT的集合。由于该解决方案涵盖了所有元素，因此它当然涵盖了尚未涵盖的所有元素。以成本OPT覆盖其余元素（证明符号中的集合CBar）意味着以成本效益OPT/|CBar 覆盖每个元素|根据成本效益（又名价格）的定义。由于最优解包含一个覆盖所有剩余元素的集合，假设我们从最优解中选择一个集合S，它至少覆盖一个剩余元素（引理2.3中的e_k） 。请注意，我们选择的是成本效益最好的集合，因此它的成本效益必须至少与OPT/|CBar| 最优解中各集合的平均成本效益一样好。 >。最后一部分是，由于定义，
|CBar|=n-(k-1)=n-k+1作为k-1元素已经被覆盖我们正在寻找覆盖元素k。因此，S以及price(e_k)的成本效益受到OPT/(n-k+1)的限制。The algorithm is assigning a "price"
price(e)to each element of the universeUwhere that price is the cost of the setSused to coveredivided by the number of elements newly covered by the setS(any elements already covered must have been assigned a lower price by a previous set due to the definition of the algorithm).There exists an optimal solution which chooses a set of sets with total cost
OPT. As that solution covers all elements, it certainly covers whatever elements have not yet been covered. Covering the rest of the elements (the setCBarin the notation of the proof) at costOPTwould mean covering each element at cost-effectivenessOPT/|CBar|by the definition of cost-effectiveness (aka price). As the optimal solution contains a set which covers all remaining elements, suppose we pick a setSfrom the optimal solution which covers at least one remaining element (e_kin lemma 2.3). Note that we are choosing the set with the best cost-effectiveness, so its cost-effectiveness must be at least as good as the average cost-effectiveness of the sets in the optimal solution ofOPT/|CBar|.The last part is that due to the definitions,
|CBar|=n-(k-1)=n-k+1ask-1elements have already been covered and we are looking at covering elementk. Therefore, the cost-effectiveness ofSand thereforeprice(e_k)is bounded byOPT/(n-k+1).