高级计算机算法笔记

基础概念

1. 问题 $\pi$，最大化或最小化问题
2. 实例(instance) $I$
3. $I$ 的可行解集合 $S(I)$，需满足
   • 可行解 $s$ 大小为 $|I|$ 的多项式($|s|\in poly(|I|)$)
   • 多项式时间能判断解 $s$ 是否可行($s\in S(I)$)
4. 目标函数(objective function) $obj(I, s)$，需满足
   • $obj(I, s) \geq 0$
   • 给定 $I,s$ 时，目标函数能在多项式时间内算出
5. 最优解 $OPT(I)$, 算法所得解 $ALG(I)$
6. $\alpha$ 近似(factor-$\alpha$-approximation)：最小化问题为例，对于任意一个实例 $I$，算法给出的解 $s$ 都满足 $\frac{obj(I,s)}{OPT(I)} \leq \alpha$

combinatorial algorithm

Vertex Cover

算法
取所有匹配边的两个端点
[alg1]

近似比
匹配中每条边都至少需要一个端点去覆盖 $OPT \geq |M|$

$ALG \leq 2\cdot |M| \leq 2\cdot OPT$

Set Cover Greedy

算法
每次贪心选性价比最高的集合
[alg2]

近似比
对于任意一个集合 $S$，将集合中元素按照算法的覆盖顺序进行排序，得到 $u1,…,u{|S|}$。当 $u_j$ 被覆盖时，$S$ 中未被覆盖的元素数量大于 $|S|-k+1$，此时 $S$ 性价比为 $C(S)/(|S|-j+1)$。$price(u_j)$ 为最优性价比，不大于 $C(S)/(|S|-j+1)$。

假设最大集合大小为 $k$，令 $Hj = \sum{i=1}^{j} \frac{1}{j}$，假设最优解选取集合 $S1,…,S_m$。$ALG=\sum{u\in U} price(u) \leq \sum{i=1}^{m} \sum{j=1}^{|Si|} price(u_j) \leq \sum{i=1}^{m} C(Si) \cdot H{|S_i|} \leq OPT \cdot H_k$

tight analysis
[tight1]

Steiner Tree

Metric Steiner Tree Problem
在原有问题上限制了图需要满足两个性质：

• 图为完全图
• 对于任意三个点 $u,v,w$ 都存在 $c(u,w)\leq c(u,v)+c(v,w)$

近似保持规约
对于 Steiner Tree 中的任何一个 $I_1$，在 Metric Steiner Tree 中都对应一个 $I_2$，$I_2$ 中的 $c_2(u, v)$ 为 $I_1$ 中 $u, v$ 的最短路长度。$I_1$ 中的最优解在 $I_2$ 中为合法解且代价根小，所以有 $OPT(I_2)\leq OPT(I_1)$。

对于 $I_2$ 中的任意一个解 $t$，将该解中的每条边 $(u, v)$ 对应于 $I_1$ 中 $u, v$ 的最短路并将其加入 $I_1$ 问题中的解 $s$ 中。$s$ 为 $I_1$ 的一个合法解，并且有 $c_1(s) \leq c_2(t)$。

如果 Metric Steiner Tree 有近似比为 $\alpha$ 的算法，那么对于 Steiner Tree 中的任意一个 $I_1$ 在转化为 $I_2$ 后用该算法求解得到解 $t$，解 $t$ 对应的解 $s$ 也一定满足 $\alpha$ 近似。因为 $\frac{ALG_1}{OPT_1} = \frac{c(s)}{OPT_1} \leq \frac{c(t)}{OPT_2} = \alpha$。

算法
在对应的 Metric Steiner Tree 中构造 Terminal 节点的导出子图（只保留这些节点和这些节点之间的边），选择导出子图的最小生成树作为解，并将其对应于原问题中。

近似比
$T$ 为经过每条最优解边两次的一个欧拉路。

根据 Metric 性质，欧拉路中每两个相邻（访问顺序上的相邻） Terminal 节点 $u, v$ 的直接连边 $(u,v)$ 都小于欧拉路中 $u,v$ 的距离。选择欧拉路中每个相邻 Terminal 节点的直接连边，构造出包含所有 terminal 节点的 Hamilton 回路 $H$。

$B$ 为由 terminal 节点导出子图的最小生成树

$$ALG_2 = c_2(B) \leq c_2(H) \leq c_2(T) = 2 \cdot OPT_2$$

tight analysis
[tight2]

Multiway Cut

算法
对于一个 terminal 节点 $t_i$ 的 isolating cut 为使 $t_i$ 与其他 terminal 节点都不连通的割。

假设有 k 个 terminal 节点，对每个 $t_i$ 计算的最小 isolating cut $C_i$，选择最便宜的 k-1 个最小 isolating cut 取并集。

[alg3]

近似比

设最优解为 $A$，令 $K_i$ 为割去 $A$ 后 $t_i$ 所在的连通块， $A_i$ 为 A 中与 $K_i$ 相连的边。根据最小 isolating cut 的定义，有 $c(C_i) \leq c(A_i)$。因为 $A$ 中每条边都跨过两个连通块并被计算两次，有 $\sum c(A_i) = 2*c(A)$。

假设代价最大的 cut 为 $C1$，那么有 $ALG= \sum{i=2}^{k} c(C_i) \leq (1-\frac{1}{k}) \sum c(C_i)$

$$ALG \leq (1-\frac{1}{k}) \sum c(C_i) \leq (1-\frac{1}{k}) \sum c(A_i) = (2-\frac{2}{k}) \cdot OPT$$

tight analysis
构造 k 阶完全图，并在每条边中间加一个节点。
[tight3]

LP-base algorithm

Linear Programs 相关概念

在多个线性不等式的限制下对线性目标函数进行优化。

一般形式
假设 prime program 为最小化问题

minimize $c^{T}x$ \
subject to

$$Ax \geq b \\ x \geq 0$$

dual program

maximize $b^{T}y$ \
subject to

$$A^{T}y \leq c \\ y \geq 0$$

LP-Duality

如果 $x^$ 为 primal program 的最优解，$y^$ 为 dual program 的最优解，那么有$\sum{j=1}^{n} c_j x^{*}{j} = \sum{i=1}^{m} b_i y^{*}{i}$。

weak LP-Duality:

如果 $x$ 为 primal program 的可行解，$y$ 为 dual program 的可行解，那么有$\sum{j=1}^{n} c_j x{j} \geq \sum{i=1}^{m} b_i y{i}$。

证明：

$$\sum_{j=1}^n c_jx_j \geq \sum_{j=1}^n(\sum_{i=1}^m a_{ij}y_i)x_j = \sum_{i=1}^m(\sum_{j=1}^n a_{ij}x_j)y_i \geq \sum_{i=1}^m b_i y_i$$

Complementary Slackness

如果 $x$ 为 primal program 的最优解，$y$ 为 dual program 的最优解，当且仅当：
Primal CS: 对于每个 $j=1,…,n$，满足 $xj=0$ 或 $\sum{i=1}^{m} a{ij} y_i =c_j$。
Dual CS: 对于每个 $i=1,…,m$，满足 $y_i=0$ 或 $\sum{j=1}^{n} a_{ij} x_j =c_j$。

Relaxing Complementary Slackness

Max-Flow Min-Cut Theorem

最大流

构造一个从 $t$ 到 $s$ 容量无穷大的虚边

maximize $f_{ts}$
subject to

$$f_{uv} \leq c_{uv} \quad (u,v) \in E \\ \sum_{(u,v)\in E} f_{uv} - \sum_{ (v,z) \in E} f_{vz} \leq 0 \quad v \in V \\ f_{uv} \geq 0 \quad (u,v) \in E$$

最小割

minimize $\sum{(u,v)\in E} d{uv} c_{uv}$
subject to

$$d_{uv} - p_{u} + p_{v} \geq 0 \\ p_{s} - p_{t} \geq 1 \\ d_{uv} \geq 0 \\ p_{v} \geq 0$$

第一行不等式系数为 $d{uv}$，为 $1$ 表示割开，为 $0$ 表示不割
第二行不等式系数为 $p{v}$，为 $1$ 表示与 $s$ 连通，为 $0$ 表示与 $t$ 连通

set cover LP-Rounding

ILP 形式

minimize $\sum_{S \in \mathcal{s}} C_S x_S$
subject to

$$\sum_{u\in S} x_S \geq 1 \quad u \in U \\ x_{S} \in \{0, 1\} \quad S \in \mathcal{S}$$

算法
在实数域上进行对上述 ILP 做线性规划，设解为 $x$。令 $f$ 为最多的点在集合中的出现次数，如果 $x_j< \frac{1}{f}$ 则设 $x_j$ 为 0，否则为 $1$。
[alg4]

对于任意一个 $u$，一定存在一个 $S$ 满足 $u \in S$ 且在线性规划解中 $x{S} \geq \frac{1}{f}$，所以在 rounding 之后依然能满足 $\sum{u\in S} x_S \geq 1$。

近似比
rounding 后每个 $xS$ 最多在线性规划解上扩大 $f$ 倍，所以 $ALG = \sum{S \in \mathcal{s}} CS x_S \leq f \cdot OPT{LP} \leq f \cdot OPT$

set cover Prime Dual Schema

算法
令 ILP 中第一行不等式系数为 y，每次任选一个未被覆盖的点 $u$，增加对应系数 $y_u$，直到有集合满足 Prime CS，并选择该集合。
[alg4]

近似比
令 $f$ 为最多的点在集合中的出现次数，$\sum{u \in S} x_S$ 表示点 $u$ 被集合覆盖次数，满足 $\sum{u \in S} x_S \leq f$(Relaxed Dual CS)。

$ALG= \sum{S\in \mathcal{S}} x_S c_S = \sum{S\in \mathcal{S}} xS \sum{u \in S} yu = \sum{u \in U} yu \sum{u \in U} xS \leq f \sum{u\in U} yu \leq f \cdot OPT{LP} \leq f \cdot OPT$

tight analysis
算法满足 tight 性质，证明略。

set cover Dual Fitting

算法
同 set cover greedy 算法

近似比
根据贪心策略选取 $yu$，当 $y_u=price(u)$ 时不满足 dual 条件，但 $y_u=\frac{price(u)}{h_k}$ 时满足 dual 条件。根据贪心证明方法，$price(u_i)\leq \frac{c(S)}{|S|-i+1}$，有 $\sum{i=1}^{|S|} y_{u_i} \leq \c(S)$。

$ALG=\sum{u \in U} price(u) = H_k \cdot \sum{u \in U} yu \leq H_k OPT{LP} \leq H_k OPT$

scheduling on parallel machines

ILP 形式
minimize $t$
subject to

$$\sum_{M_i \in \mathcal{M}} x_{ij} = 1 \quad J_j \in \mathcal{J}\\ \sum_{J_j \in \mathcal{J}} x_{ij} p_{ij} \leq t \quad M_i \in \mathcal{M} \\ x_{ij} \in {0,1} \quad M_i \in \mathcal{M}, J_j \in \mathcal{J}$$

算法
使用 parametre pruning 技巧，引入变量 $T$ 计算 OPT 的下界。定义 $ST = {(i, j) | p{ij} \leq T}$，定义 $LP(T)$ 为：

$$\sum x_{ij} = 1 \quad J_j \in \mathcal{J} \\ \sum x_{ij} p_{ij} \leq T \quad M_i \in \mathcal{M} \\ x_{ij} \geq 0 \quad (i,j) \in S_T$$

算法二分出最小的满足 $LP(T)$ 有解的 $T$，记为 $T^{}$。根据 $LP(T^{})$ 的解构造答案，在点集 $J \cup M$ 上构造二分图 $H$，当 $x{ij} \neq 0$ 时，将 $i,j$ 之间连边。令 $F$ 表示被分割过的 job 集合，在点集 $F \cup M$ 上构造二分图 $H$，当 $x{ij} \in (0,1)$ 时，将 $i,j$ 之间连边。

[alg15]

近似比
当未被分割过的 job 被分配完后，此时满足 $LP(T^{})$ 的限制，时间不超过 $T^{}$。因为被分割过的 job 是按照图上的匹配进行分配，所以每个机器最多一个 job，并且 $p_{ij} \leq T^{}$。所以 $ALG \leq 2 \cdot T^{} \leq 2 \cdot OPT$。

Maximum Satisfiability

算法

1. 随机算法
   对于每个变量随机赋值 0 或 1

2. 去随机化技巧
   分别计算 $x_1$ 为 0 或 1，$x_2,…x_n$ 随机时的条件期望，根据较大的条件期望决定 $x_1$ 取值。

决定了 $x_1,…,x_i-1$ 时，计算 $x_i$ 的条件期望，并根据较大的条件期望决定 $x_i$ 取值。

1. 整数规划
   对于第 j 个子句中未取反的变量集合记为 $P_j$，取反的变量集合记为 $N_j$。

maximize $\sum{j=1}^{m} w_j z_j
subject to

$$\sum_{i\in P_j} y_i + \sum_{i \in N_j} (1-y_i) \geq z_j \quad j=1,...,m \\ y_i \in \{0, 1\} \quad i=1,...,n \\ z_j \in \{0, 1\} \quad j=1,...,m$$

假设 $(y^{}, z^{})$ 为实数域上的 LP 最优解，对于变量 $x_i$ 以 $y^{*}_i$ 的概率设为 1，否则设为 0。

同样可以应用去随机化技巧

1. 综合算法
   以 $\frac{1}{2}$ 的概率，随机选取 1,2 算法中的一个求解。

近似比

1. 随机算法

令 $Y_j \in {0, 1}$ 表示子句 $C_j$ 是否为真，$l_j$ 表示子句 $C_j$ 的长度，$W$ 表示被满足子句的权值之和。$\mathbb{E}(Y_j) = 1-(1/2)^{l_j} \geq \frac{1}{2}$。

$\mathbb{E}(ALG) = \mathbb{E}(\sum{j=1}^{m} w_j Y_j) = \sum{j=1}^{m} wj\mathbb{E}(Y_j) \geq \frac{1}{2} \sum{j=1}^{m} w_j \geq \frac{1}{2} OPT$

1. 去随机化技巧
   假设 $x_i$ 被设为 $b_i$，有 $\mathbb{E}(W|x_1=b_1) \geq \mathbb{E}(W) \geq \frac{1}{2} OPT$。

如果 $\mathbb{E}(W|x_1=b_1,…,x_i=b_i) \geq \frac{1}{2} OPT$，类似可以推导出 $\mathbb{E}(W|x_1=b_1,…,x_i+1=b_i+1) \geq \mathbb{E}(W|x_1=b_1,…,x_i=b_i) \geq \frac{1}{2} OPT$。使用数学归纳法即可证明。

1. 整数规划
   $Pr(Yj=0) = \prod{i \in Pj} (1-y^{*}_i) \prod{i \in Nj} y^{*}_i$。根据几何平均数小于算术平均数，有 $Pr(Y_j=0) \leq (\frac{1}{l_j}(\sum{i \in Pj} (1-y^{*}_i)+\sum{i \in Nj} y^{*}_i))^{l_j}=(1-\frac{1}{l_j}(\sum{i \in Pj} y^{*}_i+\sum{i \in N_j} (1-y^{}_i))^{l_j}\leq (1-\frac{z_j^{}}{l_j})^{l_j}$。

将 $Pr(Yj=1)= 1- (1-\frac{z_j^{}}{l_j})^{l_j}$ 写成函数形式 $f(z^{}_j)$，该函数在 $[0, 1]$ 上为凸函数，有 $f(z{j}^{}) \geq f(1)\cdot z_{j}^{} +f(0) \geq (1-(1-\frac{1}{l_j})^{l_j}) z_j^{} \geq (1-\frac{1}{e}z^{}_j)$。

$\mathbb{E}(ALG) = \sum{j=1}^{m} Pr(Y_j=1) \cdot w_j \geq (1-\frac{1}{e}) \sum{j=1}^{m} wj z^{*}_j = (1-\frac{1}{e}) OPT{LP} \geq (1-\frac{1}{e}) OPT$

1. 综合算法
   [fml1]

[fig1]

最终可以得出算法的近似比为 $\frac{3}{4}$。

local search

Max Cut

算法
[alg13]

近似比
假设 $S$ 为算法得到的局部最优解，令 $\delta(S)$ 表示集合 $S$ 对应的 cut 集合。对于任意一个点 $v$，有 $w(\delta(S) \cup \delta(v)) \geq w(\delta(v)) /2$；否则将 $v$ 放入另一边能使目标函数更大。

$ALG = \frac{1}{2} \sum w(\delta(S) \cup \delta(v)) \geq \frac{1}{2} \sum w(\delta(v)) /2 = \frac{1}{2} w(E) \geq \frac{1}{2} OPT$

Submodular Function Maximization

算法
[alg14]

近似比
引理：假设 $f$ 为定义在集合上的非负 submodular 函数，令 $A \subset B \subseteq V$。那么有：

• 当 $f(B)>f(A)$ 时，一定存在 $v \in B \A$ 满足 $f(A+v)-f(A) \geq \frac{1}{|B\A|} (f(B)-f(A))$
• 当 $f(A)>f(B)$ 时，一定存在 $v \in B \A$ 满足 $f(B-v)-f(B) \geq \frac{1}{|B\A|} (f(A)-f(B))$

假设 $S$ 为算法得到的局部最优解，$S^{}$ 为最优解，根据引理有 $f(S) \geq f(S \cup S^{})$ 和 $f(S) \geq f(S \cap S^{*})$。

$2f(S) +f(V\S) \geq f(S \cup S^{}) + f(S \cap S^{}) + f(V\S)$。将后两项根据 submodular 性质放缩，得到 $2f(S) +f(V\S) \geq f(S \cup S^{}) + f(S^{}\S) + f(V) \geq f(S \cup S^{}) + f(S^{}\S)$。继续按照 submodular 性质放缩，得到 $2f(S) +f(V\S) \geq f(S^{*}) + f(\emptyset) \geq OPT$。根据鸽笼原理 $\max{f(S), f(V\S) } \geq OPT\3$。

当函数 $f$ 满足 symmetric 性质时，$2f(S) \geq f(S \cup S^{}) + f(S \cap S^{}) = f(S \cap S^{}) + f(v \ (S \cup S^{})) = f(S \cap S^{}) + f(S^{} \ S) \geq f(S^{*}) + f(\emptyset) \geq OPT$。因此 $f(S) \geq OPT/2$

Polynomial Time Approximation Scheme

PTAS 相关概念

PTAS

FPTAS

Pseudo-Polynomial Algorithm

Snapsack PTAS

算法
根据 $\varepsilon$，按比例 $K=\frac{\varepsilon P}{n}$ 缩小所有物品的价值，并按照新的价值求解。
[alg8]

近似比
令最优解选取物品 $o_1,…,o_k$。$K \sum profit’(o_i) \geq \sum profit(o_i) - kK \geq OPT -nK= OPT-\varepsilon P$。

因为 $S’$ 为缩小后的最优解，$ALG= profit(S’) \geq K profit’(S’) \geq K \sum profit’(o_i) \geq OPT-\varepsilon P$。

根据 $OPT \geq P$，有 $ALG = profit(S’) \geq OPT - \varepsilon P \geq (1-\varepsilon)\cdot OPT$。

时间复杂度
缩小后物品的最大价值为 $\frac{n}{\varepsilon}$，根据背包问题的时间复杂度，该算法为 $O(n^{3}/\varepsilon)$

Max cut PTAS

算法
[alg17]

近似比
$ALG \geq \frac{1}{2(1+\varepsilon/4)} OPT$

时间复杂度
$O(\frac{1}{\varepsilon}n \log n)$

clustering and facility location

k-center clustering parametre pruning

$c(v, S)$ 表示 $v$ 到 $S$ 中点的最近距离。找出 $k$ 个点的集合 $S$，使得 $cost(S) = \max_{v \in V} c(v, S)$ 最小

算法
使用 parametre pruning 技巧，将边集 $E$ 按照长度从小到大排序，得到 $e_1, e_2, …, e_m$，一定存在某个 $j$ 满足 $opt = c(e_j)$。

从小到大枚举 $j$， 考虑 $e_1,e_2,..,e_j$ 构成的子图 $G_j$，如果其最小支配集大小不大于 $k$，该支配集为最优解并且 $OPT=c(e_j)$。但一般图找最小支配集 NP 难，需要近似方法。认为如果极大独立集大小不大于 $k$，则认为该独立集为近似解。

因为极大独立集属于支配集，所以该近似解合法。

[alg6]

近似比

假设 $OPT=cj$，构造 $G_j$ 的平方图 $G_j^2$（将原图所有距离小于 2 的点对连边），在 $G_j^2$ 中 $max{e \in E} c(e) \leq 2 c_j$。

考虑每个 $G_j$ 最小支配集中的点 $v$，$v$ 与 $v$ 支配的点在 $G_j^2$ 中构成团。因为一个团中最多包含一个独立集中的点，所以在 $G_j^2$ 中的任意独立集都小于 $G_j$ 中的最小支配集。

假设 $i$ 为满足 $c_(e_i) \leq 2 \cdot OPT$ 的最大整数，那么 $G_j^2 \subseteq G_i$。$G_i$ 的极大独立集 $\leq$ $G_j$ 的最小支配集 $\leq k$。

$ALG \leq c(e_i) \leq 2 \cdot c(e_j) = 2 OPT$

k-center Gonzalez’s algorithm

算法
[alg9]

近似比

引理：对于任意 $k+1$ 个点，如果任意两点距离都大于 $2R$，那么一定有 $OPT>R$。假设 $OPT\leq R$，那么存在 $k$ 个中心 $c_1,…,c_k$ 将所有点分为 $k$ 类 $C_1,…,C_k$，使得 $d(c_i, C_i) \leq R$。那么一个有两个距离大于 $2R$ 的点属于同一类，与引理中的假设矛盾。

假设 $ALG > 2 \cdot OPT$，那么存在一个 $p \notin C$ 满足 d(p, C) > 2\cdot OPT$。根据算法，对于 $c_1,c_2,…,c_k, p$ 这些点，任意两点距离都大于 $2 \cdot OPT$，与引理矛盾。所以有 $ALG \leq 2 \cdot OPT$。

k-center Hochbaum-Shmoys approach

算法
[alg10]
二分查找满足 $|C| \leq k$ 的最小的 $R^{*}$，

近似比
当 $R^{} \leq OPT$ 时一定有 $|C|\leq k$，可以通过上文类似的反证法证明，所以 $R^{} \leq OPT$。根据算法，$ALG \leq 2 \cdot R^{*} \leq 2 \cdot OPT。

k-median

算法
随机初始解 $S_0$。每次考虑将 $S$ 中一个点与 $V/S$ 中一个点交换的所有情况，如果某次交换能使目标函数更小，则进行交换并更新 $S$。直到没有交换操作使得目标函数更小，算法停止。

近似比
令 $S^{}$ 为最优解，定义 $A_i=d(j, S)$，$O_j=d(j, S^{})$，
$\varphi(i), \varphi^{}(i)$ 分别表示 $S, S^{}$ 中距离 $i$ 最近的点，
$N(i), N^{}(i)$ 分别表示距离 $\varphi(i), \varphi^{}(i)$ 最近的点的集合。

k-means

算法

1. Lloyd’s algorithm
   [alg11]

2. $D^{2}$-sampling
   [alg12]

近似比
Lloyd’s algorithm 结果与最优解没有近似关系，采用 $D^{2}$-sampling 的 Lloyd’s algorithm 近似比为 $8(\ln k + 2)$。证明略。

facility location

ILP 形式
minimize $\sum fi y_i + \sum \sum d(i, j) x{ij}$

subject to

$$\sum_{i} x_{ij} = 1 \\ x_{ij} \leq y_i x, y \in \{0, 1\}$$

算法
[alg16]

近似比
令 $B(j, d)$ 表示在 $j$ 点 $d$ 范围内的设施集合，$ALG_F, ALG_C$ 分别表示算法近似解中开启设施和连接设施的费用。

引理1：$ALGF \leq 2 \sum f_y y_i$。根据马尔可夫不等式，$\sum{i\in B(j,\alphaj/delta) y_i} \geq 1-\delta$。令 $\delta = \frac{1}{2}$，可以推出在 $B(j, 2\alpha_j)$ 中最便宜的设施 $cheap{j}$ 一定有 $f{cheap{j}}\leq 2\sum 2\sum_{j\in B(j, 2\alpha_j)} f_i y_i$。因为对于每个 $i$，$y_i f_i$ 最多会被一个设施计算，所以 $ALG_F = 2 \sum f_y y_i$。

引理2：$ALGC leq 6 \sum \alpha_j$。考虑被分配到设施 $i$ 的点 $j’$，$d(i,j’) \leq 4 \alpha_j + 2\alpha{j’} \leq 6\alpha j’$。 $ALG \leq 6 \sum_{j} \alpha_j$。

综上，$ALG \leq 6 \cdot OPT_{LP} \leq 6 \cdot OPT$