CS 170 2023 年秋季作业 14（选做）

算法描述： 均匀随机地采样 \(t\) 条 TSP 巡回，用线性扫描找出其中代价最低的一条并返回。下面的正确性证明将确定所需的 \(t = \Theta(\log(1/\delta))\)。

正确性证明： 该算法返回一条优于大多数的巡回，当且仅当所采样的 \(t\) 条巡回中至少有一条是优于大多数的。单条随机巡回是优于大多数的概率为 \(0.01\)。设 \(B_1,\ldots,B_t\) 为对应事件，其中 \(B_i\) 表示第 \(i\) 条采样的巡回是优于大多数的。那么

\[ P(\text{至少一条优于大多数}) = P(B_1 \cup \cdots \cup B_t) = 1 - P(B_1 \cap \cdots \cap B_t) = 1 - (0.99)^t \ge 1 - \delta. \]

由 \(1-0.99^t \ge 1-\delta\) 得 \(\delta \ge 0.99^t\)，即 \(t \log(1/0.99) \ge \log(1/\delta)\)，因此 \(t = \Theta(\log(1/\delta))\)。

时间复杂度分析： 有两种分析方式： 1. 若假设在任意范围内采样一个随机整数耗时常数时间，则可在 \(O(n)\) 时间内采样一条随机巡回。比较两条巡回耗时 \(O(n)\)，共进行 \(t=O(\log(1/\delta))\) 次，总时间为 \(O(n\log(1/\delta))\)。（若忽略采样巡回所需时间，同样得到此结果。） 2. 若假设采样一个随机比特耗时常数时间（即整数仅在 \(\{0,1\}\) 中选取），则采样一条随机巡回需要 \(\log (n-1)! = O(n\log n)\) 时间。如此进行 \(O(\log(1/\delta))\) 次，总时间为 \(O(n\log n\log(1/\delta))\)。

对每个顶点，我们可以选择将它放在与顶点 1 相同的一侧，或相反的一侧。这给出 \(2^{n-1}\) 种将顶点划分为两个集合的方式。随后应排除所有顶点都选择与 1 同侧的那一种划分，因为此时另一侧为空。因此答案为 \(2^{n-1} - 1\)。

设第二小最小割一侧的顶点数为 \(k\)。收缩一条横跨该割的边的概率为 \(k/m\)，但我们需要一个不依赖于 \(m\) 的答案。尽管最小度可以任意小，但其余所有顶点的度必须至少为 \(k\)（否则第二小最小割的大小将小于 \(k\)）。设 \(d_v\) 为顶点 \(v\) 的度，则

\[ m = \frac12\sum_v d_v \ge \frac{(n-1)k}{2}. \]

因此 \(k/m \le 2/(n-1)\)，取 \(\alpha = 2/(n-1)\)。

每次收缩使超顶点数量减少 1，因此 \(n\) 个顶点经过 \(n-3\) 次收缩后剩下 \(n-(n-3)=3\) 个超顶点。答案为 3。

由 (c) 知 \(c=3\)。回顾课上 Karger 收缩算法的证明：为了能在超顶点图中选出 \(S^*\)，在收缩过程中不能有任何横跨 \(S^*\) 的边被收缩——否则我们将永远缺失 \(S^*\) 中的若干条边。没有任何横跨 \(S^*\) 的边被收缩的概率的下界为

\[ \prod_{i=0}^{n-4}\left(1-\frac{2}{n-1-i}\right) = \prod_{i=0}^{n-3}\frac{n-3-i}{n-1-i} = \frac{n-3}{n-1}\cdot\frac{n-4}{n-2}\cdots\frac{1}{3} = \frac{1\cdot 2}{(n-1)(n-2)} \in \Theta\left(\frac{1}{n^2}\right). \]

在得到的 3 个超顶点的图上，由 (a) 可知共有 3 个可能的割。因此输出的割恰好是 \(S^*\) 的概率为上述概率的 \(1/3\)，即 \(\Omega(1/n^2)\)。

首先运行 Karger 算法，以 \(1-p/2\) 的概率找到一个最小割 \((S, V\setminus S)\)。然后运行收缩算法 \(T\) 次，每次收缩到 3 个超顶点后均匀随机返回三个割之一。未能找到某个特定的第二小最小割的概率至多为

\[ \left(1-\frac{1}{3}\cdot\frac{2}{(n-1)(n-2)}\right)^T \le e^{-\frac{2T}{3(n-1)(n-2)}} \le \frac{p}{2}, \]

取 \(T = \lceil (3/2)(n-1)(n-2)\rceil = \Theta(n^2\log(1/p))\) 即可满足。因此总成功概率为

\[ P[\text{找到第二小最小割}] = P[\text{找到第二小最小割}\mid\text{找到最小割}]\cdot P[\text{找到最小割}] \ge (1-p/2)(1-p/2) \ge 1-p, \]

符合要求。总运行时间为 \(\Theta(n^2\log(1/p)) = \Theta(\mathrm{poly}(n)\cdot\log(1/p))\)，同样符合要求。

设调色板为 \([\Delta+1]\)。当仍存在未分配颜色的顶点时，为其分配一个不同于其任意已染色邻居的颜色（由于调色板大小为 \(\Delta+1\) 而至多只有 \(\Delta\) 个邻居，这样的颜色必然存在）。

在 \(V'\) 上诱导出的图中，我们只关心 \(v\) 的邻居与 \(v\) 的关系。在 \(G\) 的任意一个 3-染色中，\(v\) 必须与其邻域上的颜色不同，因此该邻域上至多使用 2 种颜色，即该诱导图是 2-可染色的。

当仍存在度数 \(\ge \sqrt n\) 的顶点时：任取一个这样的顶点 \(v\)，选出 3 种从未使用过的新颜色，用其中 1 种染 \(v\)，用剩余 2 种对 \(v\) 的邻域进行 2-染色（2-染色是容易的问题）。这 3 种颜色今后不再使用，并将 \(v\) 及其邻域从图中删除。由于每次循环至少删除 \(\sqrt n\) 个顶点，因此至多执行 \(\sqrt n\) 轮，共使用 \(3(\sqrt n+1)\) 种颜色。

循环结束后，剩余子图的最大度至多为 \(\sqrt n\)，用 (a) 中的贪心策略配合 \(\sqrt n+1\) 种全新颜色进行染色。使用的颜色总数为 \(O(\sqrt n)\)。

正确性：每次对 \(v\) 及其邻域的染色在子图内合法（\(v\) 与其邻域颜色不同，邻域内部 2-染色合法）；剩余子图的贪心染色同样合法。所有颜色互不相同（高度数阶段的颜色永不重复使用，低度数阶段使用全新颜色），因此整体是 \(G\) 的一个合法 \(O(\sqrt n)\)-染色。

\(\mathcal{H}\) 是两两独立的。记 \(a\cdot x = \sum_{i=1}^k a_i x_i \bmod 2\)。按照提示，对任意 \(x\neq 0\)，不妨设 \(x_1=1\)，则

\[ \Pr_{a\in\{0,1\}^k}[a\cdot x = 0] = \Pr_{a}\left[\sum_{i=2}^k a_i x_i \equiv a_1 \pmod 2\right] = \frac12, \]

因为 \(a\) 的各比特独立，固定除 \(a_1\) 外的所有比特后，\(a_1=0\) 与 \(a_1=1\) 等概率出现，且给出 \(a\cdot x\) 的两个不同取值。

对两个不同的串 \(x\neq y\) 以及任意 \(c_x,c_y\in\{0,1\}\)，我们希望 \(a,b\) 满足

\[ a\cdot x \oplus b = c_x, \quad a\cdot y \oplus b = c_y. \]

令 \(z\in\{0,1\}^k\) 满足 \(z_i = x_i\oplus y_i\)，则可将第二个条件替换为 \(a\cdot z = c_x\oplus c_y\)。由 \(x\neq y\) 知 \(z\neq 0\)，故 \(\Pr[a\cdot z = c_x\oplus c_y] = 1/2\)。又对任意 \(a\)，\(\Pr[b = a\cdot x\oplus c_x] = 1/2\)。因此

\[ \Pr_{a,b}[h_{a,b}(x)=c_x \text{ 且 } h_{a,b}(y)=c_y] = \frac12\cdot\frac12 = \frac14, \]

满足两两独立的条件。从 \(\mathcal{H}\) 中随机选取一个哈希函数需随机选取 \(a\) 与 \(b\)，共 \(k+1\) 个比特。

\(\mathcal{H}\) 不是两两独立的。考虑输入 \((x_1,x_2)=(0,0)\) 以及任意 \((y_1,y_2)\neq(x_1,x_2)\)。则 \(h(0,0)=0\) 恒成立。因此对任意满足 \(i\neq 0\) 的 \(i,j\in[m]\)，都有 \(\Pr[h(x)=i \text{ 且 } h(y)=j]=0\)，违反了两两独立。

另解：也可取任意线性相关的 \((x_1,x_2)\) 与 \((y_1,y_2)\)（即 \(x_1y_2-x_2y_1=0\)）作为反例，因为哈希函数是线性的，\((x_1,x_2)\) 的输出决定了 \((y_1,y_2)\) 的输出。

固定 \(x,y\in\{0,1,\ldots,m-1\}\) 且 \(x\neq y\)。对任意 \(i,j\in[m-1]\)，需统计在全部 \((m-1)^m\) 个函数 \(f:[m]\to[m-1]\) 中，有多少个满足 \(f(x)=i, f(y)=j\)。

满足 \(f(x)=i, f(y)=j\) 的函数 \(f:[m]\to[m-1]\) 共有 \((m-1)^{m-2}\) 个，因为此时两个输入的输出已被固定，其余每个输入的输出可在 \(m-1\) 个值中任意选取。\(\mathcal{H}\) 中函数总数为 \((m-1)^m\)，因此随机选取这样一个函数的概率为

\[ \frac{(m-1)^{m-2}}{(m-1)^m} = \frac{1}{(m-1)^2}, \]

满足两两独立的条件。\(\mathcal{H}\) 中有 \((m-1)^m\) 个函数，区分它们需要 \(\log (m-1)^m = m\log(m-1)\) 个比特。

算法很简单：运行两个 Distinct Elements 副本。将"Yes"票的 Id 送入第一个，将所有票的 Id 送入第二个。查询比例时，返回两个数据结构的输出之比。

空间复杂度至多为 \(2\cdot S(n,\epsilon,\delta)\)，其中 \(n\) 为不同投票者的人数。

由联合界，若 Yes 票数为 \(m\)，则第一个 Distinct Elements 数据结构以 \(1-\delta\) 的概率返回 \([(1-\epsilon)m,(1+\epsilon)m]\) 内的值，第二个以 \(1-\delta\) 的概率返回 \([(1-\epsilon)n,(1+\epsilon)n]\) 内的值。因此我们的算法以 \((1-\delta)^2\ge 1-2\delta\) 的概率返回

\[ \left[\frac{1-\epsilon}{1+\epsilon}\cdot\frac{m}{n},\ \frac{1+\epsilon}{1-\epsilon}\cdot\frac{m}{n}\right] \]

内的值。当 \(\epsilon\le 1/3\) 时，\(\frac{1+\epsilon}{1-\epsilon}\le 1+3\epsilon\) 且 \(\frac{1-\epsilon}{1+\epsilon}\ge 1-3\epsilon\)，故算法的输出以至少 \(1-2\delta\) 的概率落在 \([(1-3\epsilon)m/n,(1+3\epsilon)m/n]\) 内。换言之，使用 \(O(1)\) 个该数据结构的副本仅使其总体误差保证恶化 \(O(1)\) 倍。

算法如下：使用课上讲的 Reservoir Sampling 算法从流中均匀随机采样 \(t\) 个点，返回所采样 \(t\) 个点的中位数。设置 \(t = \frac{2}{\epsilon^2}\log\frac{2}{\delta}\) 可保证以至少 \(1-\delta\) 的概率使样本中位数为 \(\epsilon\)-近似。因此算法的空间复杂度为 \(t\cdot\log(|\Sigma|)\)，其中 \(|\Sigma|\) 为样本空间的大小。

为论证正确性，将集合 \(S\) 划分为三部分：

\[ S_L := \{x \mid \mathrm{pos}(x) \le m/2-\epsilon m\}, \] \[ S_M := \{x \mid m/2-\epsilon m \le \mathrm{pos}(x) \le m/2+\epsilon m\}, \] \[ S_R := \{x \mid \mathrm{pos}(x) \ge m/2+\epsilon m\}, \]

其中 \(S_L\) 为近似中位数左侧的点集，\(S_R\) 为右侧的点集。注意，若 \(t\) 个样本中来自 \(S_R\) 与 \(S_L\) 的点数均少于 \(t/2\)，则算法返回正确结果。下面说明这些事件均为低概率事件。先考虑 \(S_L\)，\(S_R\) 的证明类似。

令 \(Z_i\) 表示如下随机变量：若第 \(i\) 个样本来自 \(S_L\) 则 \(Z_i=1\)，否则 \(Z_i=0\)。我们关心 \(\Pr(\sum_{i=1}^t Z_i > t/2)\) 有多小。注意 \(\mathbb{E}[Z_i]=1/2-\epsilon\)，因为均匀随机采样一个元素落在 \(S_L\) 中的概率为 \(1/2-\epsilon\)。利用课上的 Hoeffding 界：

\[ \Pr\left[\sum_{i=1}^t Z_i > \frac{t}{2}\right] = \Pr\left[\frac{1}{t}\sum_{i=1}^t Z_i - \left(\frac12-\epsilon\right) > \epsilon\right] \le \exp(-2\epsilon^2 t). \]

因此设置 \(t = \frac{1}{2\epsilon^2}\log\frac{2}{\delta}\) 可使以至少 \(1-\delta/2\) 的概率，来自 \(S_L\) 的元素个数少于 \(t/2\)。对 \(S_R\) 同理可证，合并两者即完成证明。