最大独立集的近似比？
approximation ratio of maximum independent set?
假设我们有一个加权网格图，我们的问题是找到最大独立集。有一个贪心算法，每次选择最重的节点并删除它和它的邻居，直到 G 的所有节点都被选择或删除。我们想证明 W(s) >= 1/4 W(T) 其中 S 是我们贪婪的结果，T 是 OPT 解决方案。
设S为贪心算法的结果，T为任意独立集，可以作为OPT。我们知道对于属于T-S的任何节点v的任何T，在S中存在一个节点v'，它是v的邻居和 w(v) <= w(v').
有没有办法证明这一点？
通过以下证明可以得到想要的结果。
令S为贪心算法生成的集合，令T为最大权重的独立集合。我们将逐步将 T 转换为 S 并限制每个转换步骤的损失。
在T\S中选择v，权重最大。根据上述问题中的陈述，S 中存在 v' 使得 w(v') >= w(v)；选择这样一个v'。设 N 为 T 中 v' 的邻域； N 包含 v 和最多 4 个顶点（因为我们有一个网格图）。由于选择了具有最大权重的 v 和 w(v')>=w(v)，我们得到 w(v')>=w(N)/4。我们设置 T':=(T\N) 并向其添加 v'。通过构造，T' 仍然是一个独立的集合，我们有 w(T') >= w(T) - (3/4)w(N).
总的来说，对于每个交换步骤，T\S 中的顶点被删除，但是添加了 S 中的节点，使得添加的总权重至少是丢失的总权重的四分之一.
此外，每个步骤中构造的集合 N 是不相交的，这意味着在每个步骤中，至少保留了 w(N) 的四分之一。总的来说，正如我们构建的 S，S 的权重至少为 (1/4)w(T).
注意输入图不必是网格图，但最大度数4即可；此外，可以通过允许任意图来推广证明，将 4 替换为最大度数 Δ，得到近似比 1/Δ。
只需使用您的最后一条语句，并将 T 视为最大独立集，您将得到以下两个结果：
- 对于
T-S 中的每个节点，如 v，在 S 中存在一个像 u 的节点是 W(v) <= W(u)。
S中的每个节点，如u，最多是T中4个节点的邻居。
现在使用它们:)
假设我们有一个加权网格图，我们的问题是找到最大独立集。有一个贪心算法，每次选择最重的节点并删除它和它的邻居，直到 G 的所有节点都被选择或删除。我们想证明 W(s) >= 1/4 W(T) 其中 S 是我们贪婪的结果，T 是 OPT 解决方案。
设S为贪心算法的结果，T为任意独立集，可以作为OPT。我们知道对于属于T-S的任何节点v的任何T，在S中存在一个节点v'，它是v的邻居和 w(v) <= w(v').
有没有办法证明这一点？
通过以下证明可以得到想要的结果。
令S为贪心算法生成的集合，令T为最大权重的独立集合。我们将逐步将 T 转换为 S 并限制每个转换步骤的损失。
在T\S中选择v，权重最大。根据上述问题中的陈述，S 中存在 v' 使得 w(v') >= w(v)；选择这样一个v'。设 N 为 T 中 v' 的邻域； N 包含 v 和最多 4 个顶点（因为我们有一个网格图）。由于选择了具有最大权重的 v 和 w(v')>=w(v)，我们得到 w(v')>=w(N)/4。我们设置 T':=(T\N) 并向其添加 v'。通过构造，T' 仍然是一个独立的集合，我们有 w(T') >= w(T) - (3/4)w(N).
总的来说，对于每个交换步骤，T\S 中的顶点被删除，但是添加了 S 中的节点，使得添加的总权重至少是丢失的总权重的四分之一.
此外，每个步骤中构造的集合 N 是不相交的，这意味着在每个步骤中，至少保留了 w(N) 的四分之一。总的来说，正如我们构建的 S，S 的权重至少为 (1/4)w(T).
注意输入图不必是网格图，但最大度数4即可；此外，可以通过允许任意图来推广证明，将 4 替换为最大度数 Δ，得到近似比 1/Δ。
只需使用您的最后一条语句，并将 T 视为最大独立集，您将得到以下两个结果：
- 对于
T-S中的每个节点，如v，在S中存在一个像u的节点是W(v) <= W(u)。 S中的每个节点，如u，最多是T中4个节点的邻居。
现在使用它们:)