为什么加权图Max-Cut问题的近似比无法低于1/2？

1/2近似比的可达性证明 #

我们可以通过两种最基础的算法证明该近似比是可以达到的：

• 随机划分算法：对图中每个顶点，独立随机分配到两个顶点子集的其中一个。对于任意一条边，两个端点被分到不同子集的概率为1/2，因此割的期望大小为总边权和的1/2。由于最优割的大小不可能超过总边权和，因此该算法的期望近似比至少为1/2。我们可以通过去随机化技术（如条件期望方法）得到确定性的1/2近似算法。
• 贪心迭代算法：依次遍历所有顶点，每次将当前顶点放到能让当前割值增加最多的子集。每次操作至少能将与当前顶点相连的边权的一半加入割中，遍历结束后最终的割值至少为总边权和的1/2，因此近似比同样为1/2。

加权图场景下近似比的下界推导逻辑 #

这里的1/2是基础组合近似算法的一个通用下界，推导逻辑如下：

构造一类特殊的带权完全图：取k个顶点的完全图，每条边的权值为1。对于任意确定性的局部决策算法（即仅根据当前顶点邻接信息做划分决策的算法），我们可以构造对抗实例，使得算法得到的割值刚好为总边权和的1/2，而最优割的大小为⌊k²/4⌋，当k趋近于无穷大时，两者的比值趋近于1/2。

如果结合复杂度假设，在独一游戏猜想（UGC）成立的前提下，Max-Cut问题的多项式时间可达到的最优近似比为Goemans-Williamson算法的0.878，不存在更好的多项式近似算法；如果仅考虑不使用半正定规划的组合算法，目前已知的最优近似比约为0.53，而1/2是该类算法的一个通用下界。

相关参考文献指引 #

你可以参考以下方向的经典资料查找详细证明：

• 近似算法经典教材《Approximation Algorithms》（Vijay V. Vazirani著），第5章专门讲解Max-Cut问题的基础近似和1/2近似比的证明
• Goemans和Williamson于1995年发表的关于Max-Cut半正定规划近似算法的经典论文，其中包含了完整的近似比上下界推导
• 计算复杂性领域关于独一游戏猜想和Max-Cut不可近似性的相关综述资料

内容的提问来源于stack exchange，提问作者feedback