algorithm - 不提供 2 近似的集合覆盖问题的输入示例

Question

我需要一些帮助来解决以下问题：

显示集合覆盖问题的输入示例，该类中显示的贪心算法不提供 2 近似值。

贪心算法：

X - 有限集

F - X 的子集族，使得并集给出 X

C - 覆盖 X 的所需最小尺寸集。

Answer 1

维基百科页面中有一个3/2近似示例，展示了集合覆盖问题的贪心算法。 我们可以看到两组集合组成。2 组（“线”），形成一个分区，每组都有一半的“点”。和其他 3 组（“矩形”），分别形成另一个分区。2、4 和 8 点。 贪心算法将选择“矩形”，因为它从最大的集合开始。 可以调整该方案以进行“更差”的近似，以“欺骗”贪心算法。
F
F

配方：绘制相同的图形，但使用 31 x 2 网格而不是 7 x 2。保持两条线各有一半的点（仍然形成一个分区），并添加两个“矩形”（两个最大的，它们右侧将分别有 16 和 32 个“点”）。贪心算法将返回 5 个“矩形”，而最优解将由两条线组成，因此近似为5/2 > 2.

请注意，此过程可以无限扩展（使用(2^n)-1 per 2网格），因此您可以证明集合覆盖的贪心算法k对于任何数字都不是 - 近似k。