如何证明这种确定性算法的近似率.(加权MAX-k-Cut)

Question

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

Answer 1

它是1/2。该特定算法可以通过将条件期望的方法应用于随机近似来获得，该随机近似独立且一致地选择每个节点的分配，从而获得期望中的总边缘权重的1/2，从而获得OPT的至少1/2。

一个比率为1/2+ε的例子可以通过取具有单位边权重的K_2，n，在一侧的两个顶点之间添加一条成本无限的边，并强制算法首先考虑它们来获得。