如何论证加权MAX-k-Cut逐顶点贪心算法的近似比？

基础问题与算法边界 #

先明确讨论的统一边界，避免歧义：

• 问题目标：对边权非负的加权无向图，将所有顶点划分为k个互不重叠的组别，最大化跨组别连接的边权总和，也就是最大割权重。
• 待分析算法的执行逻辑：按照预设的固定顺序逐个处理顶点；每处理一个顶点时，计算把该顶点放入k个组别分别能新增的割总权重（新增部分仅考虑该顶点与已经完成分组的顶点之间的边，未分配的顶点不影响当前选择），直接选择能带来最大新增割权重的组别作为该顶点的归属组，整个过程没有随机选择环节。

近似比推导的核心步骤 #

这类无随机过程的确定性贪心算法，推导近似比不需要引入期望计算，核心走“单步增量下界→全局累加→锚定最优解上界”的逻辑：

1. 单步增量的下界估计
   对任意一个待分配的顶点v，所有已分配的顶点组别是固定的。我们可以算出v放到k个组别时，分别对应的新增割权重Δ₁, Δ₂, ..., Δ_k。
   算法选择最大的那个Δ_max作为当前步骤的实际增量，根据基础不等式，最大值一定不小于所有选项的平均值，也就是Δ_max ≥ (Δ₁+Δ₂+...+Δ_k)/k。
   这里有个固定的恒等关系：不管v的邻居分布如何，把所有k个组别的新增增量加起来的总和，一定等于(k-1)乘以v和所有已分配顶点的连边总权重。原理很简单：对v的任意一个已分配邻居u，u的组别是固定的，当v选的组别和u不同时，这条边的权值会被算进新增增量，这种情况一共对应k-1个组别；选到u所在的组别时，这条边的贡献为0。把所有邻居的贡献加总，就得到总和为(k-1)*s_v，其中s_v是v连到已分配顶点的边权和。
   由此可以推出单步的增量下界：Δ_max ≥ (k-1)/k * s_v。
2. 全局累加得到算法总收益下界
   把所有顶点分配步骤的增量累加，算法最终得到的割总权重ALG，满足：
   ALG ≥ (k-1)/k * sum_v s_v
   这里sum_v s_v的实际意义是图的所有边总权重W——因为每条边只会在它的后分配顶点被处理时，被计入一次s_v，没有重复统计也没有遗漏。因此可以直接得到：ALG ≥ (k-1)/k * W。
3. 关联最优解上界得到近似比
   最大割的最优解OPT本质是从所有边里选出一部分跨组边，总权重不可能超过图的全部边权总和W，也就是OPT ≤ W。
   把这个关系代入之前的不等式，就能得到ALG ≥ (k-1)/k * OPT，也就是这个贪心算法的近似比不低于*(k-1)/k*。

近似比的判定要点 #

推导出来的下界不能直接当作最终的近似比保证，还需要从几个维度验证、确认：

• 紧性验证：需要构造对应的最坏场景输入图，让算法得到的ALG和OPT的比值刚好等于(k-1)/k，说明这个下界是可达的。比如k=2的场景，构造一个二部图：两个顶点x1、x2同属二部图的X部，连接到同一个Y部顶点y1，每条边权1，图的总边权W=2。因为是二部图，最优解是把X部全放组1，Y部放组2，此时所有边都是跨组的，OPT=2。按照x1→x2→y1的顺序跑算法：x1第一步无邻居，放到组1；x2第二步的邻居是未分配的y1，因此两个组的新增增量都是0，算法随便选一个即可，比如选到组2；到第三步分配y1时，不管选哪个组，都会和其中一个X部顶点同组，最终只能割下1单位的权重，ALG=1，比值恰好为1/2，也就是(k-1)/k的下界。这类案例证明不存在可以无限压低算法表现的输入。
• 上界排除：需要证明不存在能让ALG/OPT低于(k-1)/k的图结构——也就是之前推导的单步增量下界是严格成立的，不会因为特殊的图结构、顶点顺序出现失效。
• 边界一致性验证：针对特殊场景校验推导结果是否符合常识，比如当k等于顶点总数时，每个顶点单独成组，此时OPT=W，ALG也等于W，比值为1，和(k-1)/k的计算结果一致；当边权为0、存在孤立顶点时，算法的表现不会出现明显偏离推导下界的情况。

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