如何证明这种确定性算法的逼近比。（加权的MAX-k-Cut）

Question

加权 MAX-k-CUT 问题要求在加权无向图中进行最大加权切割。 假设现在每个顶点都被一一贪婪地分配给可以最大化新切割总权重的组。 如何知道确定性算法的逼近率？

Answer 1

是 1/2。这个特定的算法可以通过将 method of conditional expectations 应用到随机近似值来获得，该近似值随机地独立且均匀地选择每个节点的分配，从而获得期望总边缘权重的 1/2，因此至少获得 1/2选择。

比率为 1/2 + ε 的示例可以通过采用具有单位边权重的 K_2,n，在一方面并强制算法首先考虑它们。