最大割问题

最大割问题 (Maximum Cut)

最大割问题（Maximum Cut Problem, MAX-CUT）是组合优化与理论计算机科学中的经典NP-hard问题。给定一个带权无向图 $G = (V, E, w)$，其中 $w_{ij} \geq 0$ 为边 $(i, j) \in E$ 的非负权重，目标是将顶点集 $V$ 划分为两个不相交的子集 $(S, V \setminus S)$，使得跨越两个子集的边的权重之和最大化。

数学形式上，引入二值变量 $x_i \in \{-1, +1\}$ 表示顶点 $i$ 的分组归属，则最大割问题等价于：

等价地，可表述为二次整数规划 $\max_{x \in \{-1, 1\}^n} \sum_{i<j} w_{ij} (x_i - x_j)^2 / 4$。加权情形下，通常将所有边权重定义在完全图上，缺失边权重为零。

计算复杂性

最大割问题是Karp于1972年证明的21个经典NP-完全问题之一。即使权重全为1且图限制为立方图或三角自由图，问题仍保持NP-hard。在平面图上，最大割问题多项式可解——可以归约为奇偶循环问题或通过Chinese Postman Problem求解。精确算法方面，分支定界法和基于半定规划（SDP）的割平面法是主流方法论，但在超过数百个顶点的实例上已不现实。

近似算法与Goemans-Williamson SDP松弛

最大割问题的核心突破来自Goemans与Williamson于1995年提出的基于半定规划的近似算法，其近似比达到 $\alpha \approx 0.87856$，至今未被超越。

该方法的思路是：将离散约束 $x_i \in \{-1, 1\}$ 松弛为单位球面上的向量约束。令 $v_i \in \mathbb{R}^n, \|v_i\| = 1$，目标转化为 $\max \sum_{i<j} w_{ij} (1 - v_i \cdot v_j) / 2$。这是一个SDP问题，可在多项式时间内求解。得到SDP最优解后，随机选取一个超平面（其法向量均匀分布在单位球面上），按 $\operatorname{sgn}(r \cdot v_i)$ 将向量分为两组。期望近似比为 $\min_{0 \leq \theta \leq \pi} \frac{2\theta}{\pi (1 - \cos\theta)} \approx 0.87856$。

在唯一游戏猜想下，该近似比是紧的：若唯一游戏猜想成立，则对任意 $\varepsilon > 0$，不存在多项式时间的 $(0.87856 + \varepsilon)$-近似算法。

经济学与社会科学中的应用

最大割问题的数学结构在经济学多个领域有深刻映射：

市场分割与聚类分析：在产业组织中，企业进行地域性市场分割时面临的本质是图割问题。以消费者或区域为顶点，以替代性/互补性为边权，寻找最大化差异化利润的分组即为最大割。类似地，在社交网络分析中，最大化群体间极化程度自然形成加权最大割。

投资组合优化：在风险分散背景下，若以资产为顶点、以资产间协方差为边权，寻找负相关组群的最大割等价于构建最大程度对冲的资产篮子。此外，统计套利中对多空组合的划分可以建模为最大割问题。

政治经济学与选区划分：选举设计中，最大化不同选区偏好差异（以最大化代议制多样性）或最小化选区内部分裂都直接对应于最大割结构的变体。

博弈论：在联盟形成博弈中，代理人选择"加入"或"不加入"某联盟以最大化跨联盟收益时，即为最大割。特别是当效用函数为超模博弈时可建立等价关系。

与其他组合问题的联系

最大割与多个经典问题存在对偶或归约关系。$\text{MAX-2SAT}$ 可归约为最大割，这意味着任何2元可满足性的最大满足赋值问题等价于某图的最大割。最大割在统计物理学中对应Ising自旋模型的基态能量问题，哈密顿量 $H = -\sum J_{ij} s_i s_j$ 的最小化等价于权重为 $J_{ij}$ 的最大割。在运筹学中，最大割常用于电路布局设计中的线网划分、超大规模集成电路设计中的层分配，以及机器学习中的谱聚类初始化。最大割的SDP松弛为理解半定规划在离散优化中的威力提供了范本，直接启发了其后一系列基于SDP的近似算法。