集合覆盖贪婪算法（个体实例）的近似比的上界

Question

无意中，我有一种方法可以找到（并证明）贪婪算法的近似比例的上界，其中（界限）可以是针对设置封面问题的个别情况获得。对于我在图书馆中遇到的问题，此比率的界限比值更好，我们可以使用众所周知的公式来解决问题的一般情况。

是否可以以某种方式使用？或者这是一个无用的结果？

Answer 1

换句话说，您可以计算每个实例的下限。经典的CS理论方法是解决分数包装问题，该问题与集合覆盖的LP松弛是双重的：为每个要素分配一个非负成本，使得对于每个集合，该集合中元素的成本总和为最多是该套装的成本。目标是最大化元素成本的每个元素的总和。

为了提高质量（例如，不是将成本分配给单个元素，将成本分配给k个元素的子集），还有更强的放松。