我开始学习近似算法，我正在读一本关于它的书，但我不了解集合覆盖算法的分析。
有人可以解释引理 2.3 吗？很短，但是看不懂。。。
1 回答
2
price(e)该算法为宇宙中的每个元素分配一个“价格” ，U其中该价格是S用于覆盖的集合的成本e除以该集合新覆盖的元素数量S（任何已经覆盖的元素必须被分配一个较低的价格由于算法的定义，之前的集合）。
存在以总成本 选择一组集合的最优解OPT。由于该解决方案涵盖了所有要素，因此它肯定涵盖了尚未涵盖的任何要素。以成本覆盖其余元素（CBar证明符号中的集合）OPT意味着OPT/|CBar|通过成本效益（又名价格）的定义以成本效益覆盖每个元素。由于最优解包含一个覆盖所有剩余元素的集合，假设我们S从最优解中选择一个至少覆盖一个剩余元素的集合（e_k在引理 2.3 中）。请注意，我们正在选择具有最佳成本效益的集合，因此其成本效益必须至少与 的最优解中的集合的平均成本效益一样好OPT/|CBar|。
最后一部分是由于定义，|CBar|=n-(k-1)=n-k+1因为k-1元素已经被覆盖，我们正在研究覆盖元素k。S因此，和的成本效益price(e_k)是有界的OPT/(n-k+1)。
于 2012-02-10T19:28:33.660 回答