如何证明我的近似比率？

Question

假设给定一个加权图G，我们希望将其节点聚类成k个簇，使得簇间所有边的权重之和最大。我们想要一个比率 (1-1/k) 的近似算法。

我的解决方案：因为这是一个最大化问题，首先我们必须找到 OPT 解决方案的上限。令 k 为 n 并且 G 是一个完整的图，因此 OPT 将是所有边的总和及其我们可以达到的最大值。所以 OPT <= SUM（所有边）。该方法被描述为：

如果 k = n 则解决方案很简单如果 k < n 我们将所有 n 个节点视为一个不相交集，并找到通过该边连接的两个节点的最小加权边和并集不相交集。我们重复此过程，直到不相交集的数量等于 k。

最后我们至少删除了 (n-k) 条低权重边（在本例中我们的结果等于 OPT），在最坏的情况下，只有 (k-1) 条高权重边被保留以添加到结果。在这种情况下，结果是 Sum(k-1 high weighted edge)。为了证明我们的方法具有近似比 (1-1/k)，我们应该证明 (1-1/k)Sum(All) <= Sum(k-1 high weighted edge)。我怀疑这是正确的还是 not.can 谁能帮我证明一下？

Answer 1

请 k=2 然后运行您在下图中提出的解决方案：

G=(V,E) 

V={a,b,c,d} 

E={({a,b},2) , ({a,c},3) , ({a,d},1) , ({b,d},2000000) , ({c,d},2000000)}

Answer 2

设 V1, ... , Vk 是 V 上具有相同大小的初始随机聚类。现在，对于 Vi 中的每个 u 和 Vj 中的 v 具有

就足够了

W(u,Vi)+W(v,Vj) > W(u,Vj)+W(v,Vi)

将u移动到Vj，将v移动到Vi。

现在，我们有：

http://i.stack.imgur.com/8zeTI.png

如何证明我的近似比率？

how to prove my approximation ratio?

algorithm

approximation