分区优化版本的近似算法？

Question

在分区问题的优化版本中，我们希望将集合 X 分区为不相交的子集 A 和 B，这样 max(sum(A),sum(B)) 就是 minimal.A 近似算法wikipedia 中有建议，但我不明白为什么这个近似值是 4/3。

Answer 1

OPT >= sum(all)/2

考虑贪婪算法给你一些答案，如 S₁ 和 S₂ 其中：

max(sum(S₁), sum(S₂)) > 4/3 OPT

（不失一般性假设 sum(S₁) > sum(S₂)) 所以我们有：

sum(S₁) > 4/3 OPT >= 2 sum(all)/3

所以 :

sum(S₁) > 4/3 OPT >= 2 sum(all)/3 so sum(S₁) > 2 sum(all)/3

所以 :

sum(S₁) > 2 sum(S₂)

因此，当 sum(S₁) 小于 sum(S₂) 时，您必须在其中一个算法步骤中添加像 A 这样的元素到 S₁ 之后你没有向 S₁

添加任何元素

所以 A 必须大于 sum(S₂) 的最终状态（因为 A + sum(S₁) > 2 总和(S₂))

所以 A 大于当前状态 sum(S₁) （因为当前状态 sum(S₁ ) < 总和的当前状态(S₂) < 总和的最终状态(S₁) < A )

并且您的列表是按降序排序的，因此 A 必须是排序列表中的第一个元素（最大元素）。所以你的 s₁ 必须只包含 A 而你有。

你也知道 sum(OPT) >= A 因为它包含 A 或其他部分包含 A 但 sum(OPT) 大于其他部分元素的总和所以

sum(OPT) > A

但是你有：

A = sum(S₁) > 4/3 sum(OPT) > sum(OPT) > A

这是一个矛盾:)

approximation algorithm for optimization version of partitioning?