COMP5270 Assignment 2 Problem 2(d), 基于哈希函数去随机化的 MaxCut

Posted on 2026-04-18 In COMP5270 Word count in article: 1.1k Reading time ≈ 4 mins.

COMP5270 Assignment 2 Problem 2(d) 题解，解释如何用两两独立哈希函数对随机化 MaxCut 进行去随机化，以及实验结果分析。

中文题目

实现基于哈希函数的去随机化近似算法求 MaxCut。对于 \(n=2\) 到 \(100\)，在 \(K_n\) 和 \(C_n\) 上运行，记录结果（平均值、最小值、最大值、标准差），对结果进行简要评论。

Implement the derandomised approximation algorithm for MaxCut based on hash functions...

Problem 2(c) 的随机化算法依赖对每个顶点的独立随机抛硬币。去随机化（derandomization）的目标是：用确定性的算法模拟随机算法能达到的效果，而不真正使用随机性。

核心思路是：用两两独立（pairwise independent）的哈希函数替代完全独立的随机比特。虽然独立程度降低了，但足以保持可预测的期望性质。

回想随机化算法的核心：每个顶点 \(v\) 以 \(1/2\) 概率放入 \(S\)，以 \(1/2\) 概率放入 \(T\)。我们希望：

\[ \mathbb{E}[\text{割大小}] = \frac{1}{2}|E|. \]

现在考虑用哈希函数 \(h: V \to \{0,1\}\) 来决定分配。关键观察：如果 \(h\) 是 pairwise independent 的，那么对任意不同的顶点 \(u,v\)，\(h(u)\) 和 \(h(v)\) 分布是独立的（或说"成对独立"）。

对每条边 \((u,v)\)，它被割开的概率是：

\[ P[h(u) \neq h(v)] = P[h(u)=0]P[h(v)=1] + P[h(u)=1]P[h(v)=0] = \frac{1}{2}. \]

即使只有成对的独立性，这个概率关系依然成立——因为我们只需要每条边两端比特独立的概率，而不是更多。

更妙的是，由于 \(h\) 是确定性的（给定哈希函数后），我们可以直接计算任意给定 \(h\) 的割大小，不需要采样：

\[ \text{cut}(h) = \sum_{(u,v)\in E} \mathbf{1}[h(u) \neq h(v)]. \]

而对所有哈希函数（由随机种子决定）取平均，期望仍然是 \(|E|/2\)。

所以我们可以遍历所有哈希函数（或者用某种确定性方式覆盖），找出割最大的那个。由于状态空间是有限的（对于 \(p\) 素数和哈希值范围 \(m\)，共有 \((p-1)\cdot p\) 种 \((a,b)\) 组合），这在实验规模下是完全可行的。

这就是为什么输出是确定性的（平均=最小=最大），因为我们选的是所有哈希函数中割最大的那一个。

固定哈希族参数：素数 \(p\)，桶数 \(m=2\)（因为只需要把顶点映射到 \(\{0,1\}\)）
对每一对可能的 \((a,b)\)：
- 定义哈希函数 \(h_{a,b}(v) = ((a \cdot v + b) \bmod p) \bmod 2\)
- 计算该哈希函数产生的割大小
返回割大小最大的那个哈希函数对应的割值

实际上，由于课程里用的是 pairwise independent family，我们可以遍历所有 \((a,b)\) 组合。

对 \(K_n\)：割值应为 \(\lfloor n^2/4 \rfloor\)（完全图的全局最优割）对 \(C_n\)：割值应为 \(n\) 或 \(n-1\)（环图交替染色的最优割）

混淆"随机选一个哈希函数"和"遍历所有哈希函数找最优"：前者还是随机算法，后者才是确定性去随机化版本。题目要求的是后者。
哈希函数生成方式：必须保证 \(a \neq 0\)（\(a \in \{1,\dots,p-1\}\)），\(b \in \{0,\dots,p-1\}\)，用 randbelow(p-1)+1 和 randbelow(p) 实现。
参数 \(p\) 的选择：\(p\) 需要大于顶点数 \(n\)，通常用一个大素数如 \(2147483647\)（\(2^{31}-1\)）。