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

Question

在分区问题的优化版本中，我们希望将集合 X 分区为不相交的子集 A 和 B 使得 max(sum (A),sum(B)) 是最小的。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 sum (S₂))

所以 A 大于当前状态 sum(S₁) (因为当前状态 sum(S₁) < 当前状态sum(S₂) < sum(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

这是一个矛盾:)