随机算法–徐小华

随机算法作业

1. 顶点覆盖问题

问题描述

考虑下述 顶点覆盖问题 的简单随机算法：

开始时 S = ∅
While S 不是一个顶点覆盖
          选择一条没有被 S 覆盖的边 e
          随机地选择 e 的一个端点（每一个端点的可能性相等）
          把选中的结点加入 S
Endwhile

（a）这个算法是 最小权顶点覆盖问题 的 $c$-近似算法吗？其中 $c$ 是某个常数。证明你的答案。

（b）这个算法是 最小规模顶点覆盖问题 的 $c$-近似算法吗？其中 $c$ 是某个常数。证明你的答案。

（提示：用 $P_e$ 表示在这个算法中边 $e$ 作为未覆盖的边被选的概率。你能够用这些概率表示解的期望值吗？为了用这些概率给出最优值的上界，尝试给出所有与给定结点 $v$ 关联的边的概率之和的上界，即 ${\sum }_{e与v关联}{P}_e$ 的上界）

参考答案

解答

（a）不是。

一个反例是仅由一条边 $(u,v)$ 组成，假设顶点 $u$ 的权值为 1，顶点 $v$ 的权值大于 $2c$，那么最小权顶点覆盖是 1，但是该近似算法选择顶点 $v$ 的概率是 $1/2$，所以用概率表示解的期望值大于 $1/2\ast 2c$ 即大于 $c$。

（b）是。

用 $p_e$ 表示在这个算法中边 $e$ 被选的概率，注意到算法中没有指定边的选择规则，可以随机选择未覆盖的边，也可以通过最小索引等进行选择，概率 $p_e$ 显然取决于所使用的选择规则。但任何选择规则都会产生概率。

现在注意两个事实：

• 首先，$\sum _{e\in E}{p}_e$ 就是算法选择的顶点的期望个数。因为每次选择一条边 $e$ 时，就把它的一个端点加入到顶点覆盖中。

• 接下来，考虑与一个顶点 $v$ 相邻的边的概率 $p_e$ 的和。

  设 $\delta (v)$ 表示与顶点 $v$ 相邻的边的集合，考虑$\sum _{e\in \delta (v)}{p}_e$，这正是选择的与顶点 $v$ 相邻的边的期望个数。设 $S(v)$ 是选择的与顶点 $v$ 相邻的边的随机变量，有 $Exp(|S(v)|)=\sum _{e\in \delta (v)}{p}_e$。这个期望值最多是 2，因为每次选择 $\delta (v)$ 中的一条边，以 $1/2$ 的概率用顶点 $v$ 覆盖边 $e$，然后 $\delta (v)$ 中的所有边都被覆盖了，不会再有这个集合中的边被选择。为了使这个论证严密，用 $E_i$ 表示至少有 $i$ 条与顶点 $v$ 相邻的边被选择的事件。现在有以下不等式来表示选择的边的期望个数：
  $$Exp(|S(v)|)=\sum _{i}iProb(E_i-E_{i+1})=\sum _{i}Prob(E_i)\le 1+\sum _{i>1}{2}^{i-1}\le 2.$$
  不等式 $Prob(E_i)\le 2^{i-1}$ 对于 $I>1$ 成立，因为每次选择与顶点 $v$ 相邻的一条边后，以 $1/2$ 的概率把 $v$ 加入到顶点覆盖中。现在准备好了用期望的顶点覆盖的大小来限制最优解。设 $S^{\ast }$ 是一个最优的顶点覆盖。
  $$\sum _e{p}_e\le \sum _{v\in S\ast }\sum _{e\in \delta (v)}{p}_e\le \sum _{v\in S\ast }2=2|S\ast |,$$
  第一个不等式成立是因为 $S^{\ast }$ 是一个顶点覆盖，所以第二个求和必须覆盖每一条边 $e$。

综上，该算法是 最小规模顶点覆盖问题 的 $2$-近似算法。

$Exp(|S(v)|)=\sum _{e\in \delta (v)}{p}_e$。（如果对每条边 $e$ 都以概率 $p_e$ 选择它，那么与顶点 $v$ 相邻的边被选择的期望个数就是所有相邻边的概率之和。）

2. 负载均衡算法

问题描述

并行和分布式系统的 负载均衡算法 试图把一组计算任务分散到多台机器上。用这种方式，没有一台机器成为“热点”。如果能够进行某种集中的协调，那么负载可能被分散得近乎理想。如果任务来自各种不能协调的来源，那怎么办？正如我们在 13.10 节（参考教材）中看到的，一种可能的做法是把它们随机地分配给机器，并希望这种随机化能防止不均衡。显然，一般地这不能做得像集中解决那样理想，但它可能是相当有效的。现在我们打算分析 13.10 节（参考教材）中考虑的一种简单的负载均衡启发式算法的几个变形与推广。

假设有 $k$ 台机器和 $k$ 项要处理的任务。每一项任务被独立地随机分配给一台机器（每台机器的可能性相等）。

（a）设 $N(k)$表示没有接受到任务的机器的期望数，因而 $N(k)/k$ 是无事可做的机器的期望比例。极限 $li{m}_{k\to \infty }N(k)/k$ 是多少？证明你的答案。

（b）假设机器不能让剩余的任务排队等候，因而随机分配把一件以上的任务送给机器 $M$，那么 $M$ 将做它接受到的第一项任务并拒绝其余的任务。设 $R(k)$ 是被拒绝的任务的期望数，因而 $R(k)/k$ 是被拒绝的任务的期望比例。极限 $li{m}_{k\to \infty }R(k)/k$ 是多少？证明你的答案。

（c）现在假设机器有稍微大一点的缓冲器，每一台机器能做它接受的前两项任务并拒绝其他更多的任务。设 $R_2(k)$ 表示在这个规则下被拒绝的任务的期望数。极限 $li{m}_{k\to \infty }{R}_2(k)/k$ 是多少？证明你的答案。

参考答案

解答

（a）$1/e$

给定一台机器 $p$，为了使其没有任务，每个任务必须分配给不同的机器。由于任务是随机均匀分配的，给定的任务 $j$ 不被分配给 $p$ 的概率是 $(1-\frac{1}{k})$，因此 $p$ 没有被分配任何任务的概率是 $(1-\frac{1}{k}{)}^k$，因此没有任务的机器的期望数量是 $N(k)=k(1-\frac{1}{k}{)}^k$。

因此 $N(k)/k=(1-\frac{1}{k}{)}^k$，故 $li{m}_{k\to \infty }N(k)/k=1/e$。这也说明，在极限下，没有任务的机器数量为 $k/e$。

（b）$1/e$

注意到被拒绝的任务数量（用 $N_{rej}$ 表示）等于总任务数 $k$ 减去被接受的任务数 $N_{acc}$（即 $N_{rej}=k-N_{acc}$）。被接受的任务数等于 $k$ 减去没有任务的机器数 $N_{nojob}$，因为剩下的机器都会分配一个工作。因此$N_{rej}=k-N_{acc}=k-(k-N_{nojob})=N_{nojob}$。因此问题（b）的答案与问题（a）的答案相同。

（c）$10.4\%$

这部分将涉及轻微的计算。

• 由（a）知没有任务的机器数量是 $k/e$。

• 先计算只有一个任务的机器数量。给定一台机器 $p$。给定任务 $j$ 被分配给 $p$ 的概率是 $1/k$，剩余任务不被分配给 $p$ 的概率是 $(1-\frac{1}{k}{)}^{k-1}$。最后，选择“给定”任务 $j$ 有 $k$ 种选法。因此，只有一个任务被分配给该机器的概率是：

$$k\frac{1}{k}(1—\frac{1}{k}{)}^{k-1}$$

注意这也在极限 $1/e$ 内，因此只有一个任务的机器数量也是 $k/e$。

• 所以，剩下的机器均执行两个任务，机器数为 $k-\frac{2k}{e}$。

最终 $k/e$ 台机器每台有一个任务，以及 $k-\frac{2k}{e}$ 台机器每台有两个任务。从 $k$（总工作数）中减去这个数量，
$$R_2(k)=k-\frac{k}{e}-2(k-\frac{2k}{e})=\frac{k(3-e)}{e}.$$
因此，$li{m}_{k\to \infty }{R}_2(k)/k=\frac{3-e}{e}=10.4\%$。

3. MAX 3-SAT

题目描述

在 13.4 节（参考教材）我们设计了 $MAX3-SAT$ 题的一个近似到 7/8 因子的近似算法，在那里我们假设每一个子句有与 3 个不相关联的项。现在要考虑一个类似的 MAX SAT 问题，给定变量集 X = { x 1 , … , x n } X = \{x_1, … , x_n\} X={x1​,…,xn​} 上的一组子集 $C_1,\dots ,C_k$，求一个真值赋值满足尽可能多的子句。每一个子句至少有一个项，一个子句中的所有变量是不同的，除此之外对子句的长度没有做任何假设，可能有一些子句有很多变量，而另一些可能只有一个变量。

（a）首先考虑我们用于 MAX 3-SAT 的随近算法，以概率 1/2 独立地一个量为真或假。证明这个随机赋值满足的期望子句数不小于 $k/2$，即所有的子句中至少期望地有一半被满足。给出一个例子说明存在 MAX SAT 实例使得任何赋值满足的子句都不超过所有子句的一半。

（b）如果有一个只由一项成的子句（例如，仅由 $x_1,{\bar{x}}_2$ 构成的子句），那只有唯一的方法满足它：必须以适当的方式给对应的变量赋值。如果有两个子句，其中一个仅由 $x_i$ 构成，而另一个仅由它的否定项 ${\bar{x}}_i$ 构成，那么这是一个相当直接的矛盾。假设实例不含这种“冲突的子句”对，即没有变量 $x_i$ 使得有一个子句 C = { x i } C=\{x_i\} C={xi​}，又有一个子句 C ′ = { x ˉ i } C'=\{\bar x_i \} C′={xˉi​}，修改上面的随机算法把近似因子从 1/2 改进到 0.6，即修改算法使得被满足的期望子句数至少为 $0.6k$。

（c）试给一个一般 MAX SAT 题的多项式时间随机算法，使得算法满足的期望子句数不少于最大可能的 0.6。

（注意，根据部分（a）中的例子，存在不可能满足多于 $k/2$ 个子句的实例，这里的要点是仍可指望得到一个有效的算法，它能够期望地满足最优赋值能够满足的最大子句数的 0.6。）

参考答案

解答

（a）考虑一个具有 $n$ 个变量的子句 $C_i$。该子句不满足的概率为 $\frac{1}{2^m}$，因此满足的概率为 $1-\frac{1}{2^m}$。最坏情况是当 $C_i$ 只有一个变量时，即 $n=1$，此时子句被满足的概率为 $\frac{1}{2}$。由于有 $k$ 个子句，被满足的子句的期望数量至少为 $\frac{k}{2}$。考虑两个子句 $x_1$ 和 ${\bar{x}}_1$。显然只有其中一个可以被满足。

（b）对于出现在单变量子句中的变量，假设使变量满足子句的概率为 $p\ge \frac{1}{2}$。对于所有其他变量，概率与之前一样为 $\frac{1}{2}$。现在对于一个具有 $n$ 个变量的子句 $C_i$， $n\ge 2$，满足它的概率最差为 $(1-\frac{1}{2^n})\ge (1-p^2)$，因为 $p\ge \frac{1}{2}$。现在要解出 $p$，使所有子句都满足，解方程 $p=1-p^2$ 得到 $p\approx 0.62$。因此，预计满足的子句数量为 $0.62n$。

（c）令总子句数为 $k$。对于每对单一变量冲突的子句，即 $x_i$ 和 ${\bar{x}}_i$，从子句集中移除其中一个。假设移除了 $m$ 个子句，那么最多可以满足的子句数为 $k-m$。现在将之前问题中描述的算法应用于最初没有冲突的 $k-2m$ 个子句，以这种方式满足子句的期望数为 $0.62\ast (k-2m)$。除此之外，还可以满足 $2m$ 个冲突子句中的 $m$ 个子句，因此满足的子句数为 $0.62\ast (k-2m)+m\ge 0.62\ast (k-m)$，这是期望的目标。因为每个子句只考虑一次，所以该算法在变量和子句数目上是多项式级别的。