顶点封面算法误差

Question

我有以下随机算法为顶点封面问题。让 $ b_0 $ 是输出集：

• 修复了一些订单 $ e_1，e_2，。 。 。 ，e_m $ 在g的边缘设置e中的所有边缘，并设置 $ b_0=imptyset $ 。
• 添加到 $ b_0 $ 所有隔离顶点，即没有任何事件边缘。
• 对于每个边缘 $ e $ $ e_1，e_2，。 。 。 ，e_m $
  • 如果 $ e $ 未包含在 $ b_0 $ ，则
  • 翻转一个公平硬币决定要选择哪个端点，并将此端点添加到 $ b_0 $ 。

如何证明，对于每个常量 $ c \ geq 1 $ ，该算法可能会生成 $ b_0 $ 带 $ | b_0 | \ ge c | opt | $ ？

Answer 1

修复 $ c + 1 $ 顶点的星形图。星形图是连接到图表中所有其他顶点的顶点（称为中心的通用顶点），所有其他顶点都是成对的 not 相邻。这是一个可视示例。 $ c $ 是明星的中心。

现在，最佳解决方案是打包星的中心。此解决方案的大小等于1.对于每个边缘，假设我们的算法包装边缘的另一端（非通用顶点），然后我们需要包装图形的所有顶点，除了中心，因此，我们需要包装 $ c $ 不同的顶点。总共获得 $ | b_0 |= C | OPT | $ 对于 $ c $ 。

---

注意 算法的简单修改产生了替代近似算法，其答案尺寸至最佳是最佳的两倍。它如下：如果边缘的两个端点不在 $ b_0 $ ，那么将两个端点添加到 $ B_0 $ 并迭代。

这个工作简单的原因。获取其端点的边缘添加了最大匹配，因此，我们在最大匹配中添加两倍的顶点数量。注意，图中匹配的大小是最小顶点盖的大小的较小限制，因此，我们最多添加了两次的顶点，因为最小顶点盖的大小。