MAX DICUT

大白话：在一张有方向的图（谁把信息传给谁）上，把节点分成两组，让「从 A 组指向 B 组的权重之和」尽可能大——这就是 MAX DICUT。难点在于这问题本身是 NP-hard 的，实践中靠半定规划松弛加随机舍入拿到约 0.878 的近似比。

定义。 MAX DICUT = MAXimum DIrected CUT：给定有向图 G = (V, E)， 找节点划分 (A, B)（即 k=2 二分）以最大化有向 cut \sum_{u \in A, v \in B, u \rightsquigarrow v} w(u,v)。 它等价于 Laenen-Sun 2020 的 flow ratio 在 k=2 时的退化情形。

复杂度

• NP-hard（Karp 1972）
• 0.878 近似：Goemans & Williamson（J. ACM 1995）用 SDP 松弛 + 随机舍入 在 MAX DICUT / MAX CUT 上达到 0.878 的近似比。
• 在有向图上，简单近似也能达到 0.858（Trevisan 1998）；用更复杂的 SDP 可达 0.874。

与 Laenen-Sun 2020 的关系

当 k=2 时, flow ratio: \Phi_G(S_0, S_1) = \frac{w(S_1, S_0)}{\text{vol}(S_0) + \text{vol}(S_1)} + \frac{w(S_0, S_1)}{\text{vol}(S_1) + \text{vol}(S_0)} 仍等价于 MAX DICUT (NP-hard)。这意味着 Laenen-Sun 的 chain flow ratio 在 k=2 时没有多项式时间精确解， 必须用 Hermitian Laplacian 的谱松弛（近似保证由 Theorem 4.4 提供）。

邻近概念

• Flow Ratio (chain objective) — Laenen-Sun 的链式目标
• Hermitian Laplacian — 谱松弛方案
• Hermitian Spectral Clustering — 父类

起源 / 标准文献

• Karp (1972) "Reducibility among combinatorial problems" — NP-hardness
• Goemans & Williamson (1995) J. ACM — 0.878 SDP 近似
• Laenen & Sun (NeurIPS 2020) — k=2 退化分析（本 wiki 摘要）

待研究问题

• 对有向图 + 边权有噪声的 MAX DICUT 鲁棒近似？
• MAX DICUT 的量子近似算法（如量子 SDP）？