Chengyuan Ma's Blog

幽居默处而观万物之变，尽其自然之理，而断之于中

PACT 06/29 三大概率不等式以及近似算法初步

Posted on 2020-07-11

概率论初步

期望的线性性

$\mathbb{E}[X+Y] = \mathbb E [X] + \mathbb E[Y]$

随机变量的方差

$\begin{aligned} \operatorname{Var}[X] &:= \mathbb{E}\left[\left(X-\mathbb{E}[X]\right)^2\right] \\ &= \mathbb{E} \left[X^2 - 2\mathbb{E}[X]X+\mathbb{E}[X]^2\right] \\ &= \mathbb{E} \left[X^2\right] - 2\mathbb{E}[X]^2 + \mathbb{E}[X]^2 \\ &= \mathbb{E} \left[X^2\right] - \mathbb{E}[X]^2 \end{aligned}$

推论：若随机变量 X,Y 互相独立，则有：

$\operatorname{Var}[X+Y] = \operatorname{Var}[X] + \operatorname{Var}[Y]$
$\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$

（互相独立的定义： $\forall x, y, \operatorname{Pr}[X=x\cap Y=y]=\operatorname{Pr}[X=x]\operatorname{Pr}[Y=y]$ ）

马尔科夫不等式

设为非负随机变量，则 $\forall a >0$ ：

$\operatorname{Pr}[X\ge a] \le \frac{\mathbb{E}[X]}{a}$

证明：

$\begin{aligned} \mathbb{E}[X] &= \sum_{x}x\operatorname{Pr}[X=x] \\ &= \sum_{x<a}x\operatorname{Pr}[X=x] + \sum_{x\ge a}x\operatorname{Pr}[X=x] \\ &\ge \sum_{x\ge a}x\operatorname{Pr}[X=x] \\ &\ge \sum_{x\ge a}a\operatorname{Pr}[X=x] \\ &= a \sum_{x\ge a}\operatorname{Pr}[X=x] \\ &= a \operatorname{Pr}[X\ge x] \end{aligned}$

（离散形式，连续形式的证明方法类似）

其中第一个 $\ge$ 依赖于非负的特性，因此非负是必须的！

马尔科夫不等式让我们可以在只知道随机变量期望的情况下对于其分布概率进行粗略定界。

切比雪夫不等式

设为随机变量，则 $\forall a > 0$ ：

$\operatorname{Pr}\left[|X-\mathbb{E}[X]| \ge a\right] \le \frac{\operatorname{Var}[X]}{a^2}$

证明：

$\begin{aligned} \operatorname{Pr}\left[|X-\mathbb{E}[X]| \ge a\right] &= \operatorname{Pr}\left[(X-\mathbb{E}[X])^2 \ge a^2\right] \\ &\le \frac{\mathbb{E}\left[(X-\mathbb{E}[X])^2\right]}{a^2} \\ &= \frac{\operatorname{Var}[X]}{a^2} \end{aligned}$

注意到

且 $(X-\mathbb{E}[X])^2$ 非负，因此我们可以在第二步使用马尔科夫不等式。

如果我们不仅知道随机变量的期望（一阶矩），还知道其方差（二阶矩），那么切比雪夫不等式可以给出比马尔科夫不等式更为精确的上界。

切尔诺夫上界（Chernoff Bound）

设随机变量 $X=\sum_{i=1}^n X_i$ ，其中 $X_1,\cdots,X_n$ 为 [0,1] 上互相独立的随机变量，则 $\forall t>1$ ：

$\operatorname{Pr}\left[|X - \mathbb{E}[X]| \ge t\mathbb{E}[X]\right] \le 2\exp\left(-\frac{t\mathbb{E}[X]}{3}\right)$

且 $\forall \epsilon \in (0,1]$ ：

$\operatorname{Pr}\left[|X - \mathbb{E}[X]| \ge \epsilon\mathbb{E}[X]\right] \le 2\exp\left(-\frac{\epsilon^2\mathbb{E}[X]}{3}\right)$

加性切尔诺夫不等式（Additive Chernoff Bound）： $\forall b >1$ ：

$\operatorname{Pr}\left[|X - \mathbb{E}[X]| \ge b\right] \le 2\exp\left(-\frac{2b^2}{n}\right)$

三个不等式给出上界的比较

考虑如下问题：投次均质硬币，设随机变量表示头朝上的次数。估计 $\operatorname{Pr}\left[X\ge \frac{3n}{4}\right]$ ？

马尔科夫不等式：

显然， $\mathbb{E}[X]=\frac{n}{2}$ ，且非负：

$\operatorname{Pr}\left[X\ge \frac{3n}{4}\right] \le \frac{\frac{n}{2}}{\frac{3n}{4}} = \frac{2}{3}$

这个上界是很松的。

切比雪夫不等式：

设随机二元变量 X_i 表示第次投是否头朝上，则显然 $X=\sum_{i=1}^nX_i$ ，且易得 $\operatorname{Var}[X_i]=\frac{1}{4}$ ，由于 X_i 两两独立，则 $\operatorname{Var}[X]=\frac{n}{4}$ ，运用切比雪夫不等式：

$\begin{aligned} \operatorname{Pr}\left[X\ge \frac{3n}{4}\right] &= \operatorname{Pr}\left[X - \frac{n}{2}\ge \frac{n}{4}\right] \\ &= \frac{1}{2}\operatorname{Pr}\left[\left|X - \frac{n}{2}\right|\ge \frac{n}{4}\right] \\ &= \frac{1}{2}\operatorname{Pr}\left[\left|X - \mathbb{E}[X]\right|\ge \frac{n}{4}\right] \\ &\le \frac{1}{2} \frac{\frac{n}{4}}{\left(\frac{n}{4}\right)^2} \\ &= \frac{2}{n} \end{aligned}$

切尔诺夫上界：

显然，取 $\epsilon = \frac{1}{2}$ ：

$\begin{aligned} \operatorname{Pr}\left[X\ge \frac{3n}{4}\right] &= \operatorname{Pr}\left[X - \frac{n}{2}\ge \frac{n}{4}\right] \\ &= \frac{1}{2}\operatorname{Pr}\left[\left|X - \frac{n}{2}\right|\ge \frac{n}{4}\right] \\ &= \frac{1}{2}\operatorname{Pr}\left[\left|X - \mathbb{E}[X]\right|\ge \frac{1}{2}\mathbb{E}[X]\right] \\ &\le \exp\left(-\frac{1}{12}\cdot \frac{n}{2}\right)\\ &= \exp\left(-\frac{n}{24}\right) \end{aligned}$

各上界的效果：

看来这个例子里面还是切比雪夫不等式给出的上界最好——是不是切尔诺夫上界我学到的形式本身太loose了？

近似算法初步

定义

若算法满足以下条件，则称算法是某个问题（不妨假设是最小化问题）的 $\alpha$ 近似比的近似算法：

是多项式时间的。
对于所有输入，的输出 $\operatorname{soln}(A) \le \alpha \cdot\mathrm{OPT}$ ，其中 $\mathrm{OPT}$ 是该输入的最优解。

对于最大化问题，第二个条件为 $\operatorname{soln}(A) \ge \frac{1}{\alpha} \cdot\mathrm{OPT}$ 。

（继续假设是最小化问题）

显然，为了精确计算 $\alpha$ 我们必须知道 $\mathrm{OPT}$ ，而这显然是不现实的（如果可以我还要近似算法干嘛？），因此我们退而求其次寻找 $\mathrm{OPT}$ 的一个比较紧的下界，我们的解与该下界之比自然就是 $\alpha$ 的上界了。

例：最小顶点覆盖问题

输入： G=(V,E)

目标：最小化点集 $S\subseteq V$ ，同时满足 $\forall (u,v) \in E$ ， $u\in S$ 或 $v \in S$ 。

这是一个知名的NP Complete问题。在这里我们设计一个简单的近似算法。然而令人吃惊地是，的近似比已经是我们目前能够做到的最好结果！

思路：考虑的一个极大匹配，显然极大匹配是可以在多项式时间内求出的。

同时注意到，任意无向图极大匹配的大小必定是其点覆盖集大小的下界，因为点覆盖必须取极大匹配当中每一条边的至少一个端点才能完成覆盖！

算法：

计算的一个极大匹配。
取极大匹配所有边的所有端点为。

为什么正确？考虑反证：若 $\exists (u,v) \in E$ ，使 $u\not\in S$ 且 $v \not \in S$ ，那显然边 (u, v) 还可以加入，这和的极大性是矛盾的。

近似比证明：

$\begin{aligned} |S| = 2|M| \le 2\cdot \mathrm{OPT} \end{aligned}$

得证。

PACT 07/06 线规舍入 + 背包问题

Posted on 2020-07-11

线性规划舍入（LP Rounding）

对于很多的 $\mathsf{NP}$ 问题，我们都可以写出一个对应的整数规划（IP），然而写成整数规划本身没有啥用，因为整数规划也是 $\mathsf{NP}$ 的。但是整数规划可以通过松弛转变为线性规划，后者是可以在多项式时间内求解的，这就给近似算法的设计提供了一个思路。

唯一的问题是，线性规划给出的解未必就是整数了（在例如网络流问题等特殊的问题下还是有可能的），因此我们需要在确保解的可行性的前提下对于线性规划的解进行舍入，这个技巧便成为LP rounding。

以带权顶点覆盖问题为例，其整数规划为

$\begin{aligned} \text{minimize}\quad &\sum_{v\in V}c_vx_v \\ \text{subject to}\quad &x_u+x_v\ge 1\quad \forall (u, v)\in E \\ &x_v \in \{0,1\}\quad \forall v\in V \end{aligned}$

表示

是否被选入覆盖集当中。

其松弛后的线性规划为

$\begin{aligned} \text{minimize}\quad &\sum_{v\in V}c_vx_v \\ \text{subject to}\quad &x_u+x_v\ge 1\quad \forall (u, v)\in E \\ &x_v \ge 0\quad \forall v\in V \end{aligned}$

显然这个线性规划在有的时候不会给出整数解，例如对于一个三角形，整数规划会给两个顶点的

赋

，而线性规划会给三个顶点赋 $\frac{1}{2}$ 。

于是就需要舍入。如何舍入？设线性规划最优解 $x_v^*\ge \frac{1}{2}$ 时，整数规划的解 $\hat x_v$ ，则

$\hat x_v = \begin{cases} 1,&x_v^*\ge \frac{1}{2} \\ 0,&x_v^*< \frac{1}{2} \end{cases}$

由于我们的约束 $x_u+x_v\ge 1$ ，

当中至少有一个 $\ge \frac{1}{2}$ ，因此这么舍入后的解依然是可行解。

注意到如果按照这么舍入， $\hat x_v \le 2x_v^*$ ，又注意到线性规划的最优解一定不大于原整数规划的最优解，即 $\mathrm{OPT}$ ：

$\sum_{v\in V}c_v\hat x_v \le \sum_{v\in V}2c_vx_v^* = 2\sum_{v\in V}c_vx_v^* \le 2\cdot\mathrm{OPT}$

因此我们的算法就是一个

倍近似算法。这个算法较之前极大匹配算法的优势在于其可以很好地处理点带权的情况。

背包问题

定义

输入：件物品，每一件物品有重量 w_i 和价值 p_i ，以及背包容量。

目标：在物品总重不超过背包容量的前提下使得打包的物品价值总和最大。

贪心算法

一个非常简单直接的想法是按照价重比（ $\frac{p_i}{w_i}$ ）贪心，但是这个贪心非常容易被卡掉，比如说有两个物品，第一件物品的重量为，价值为 $1+\varepsilon$ ，第二件物品的重量和价值都是，那按照价重比贪心我会先选第一件，然后之后就不能选第二件了，这个方案就很糟糕，而且和最优解的差距可以任意大。

但是有一个简单的小优化：假设物品是我们第一个因为放不下不选的物品，我们最后在贪心的方案和物品单件中择优输出，这个算法一下子就会好上很多——事实上这就是一个倍近似算法了。

证明：分两种情况。

贪心方案的总重 $> \frac{W}{2}$ 。因为我们是按照价重比贪心的，因此最优解的总价重比不会大于我们贪心方案的价重比，而贪心方案的重量至多是，因此此时我们贪心方案的总价值至少为最优方案的 $\frac{1}{2}$ 。
贪心方案的总重 $\le\frac{W}{2}$ 。装不下下一个，说明接下来的物品是重量 $>\frac{W}{2}$ 的大块头，令这个物品为。这样的大块头在任何打包方案当中都至多塞一个。此时最优解总价值不大于当前贪心解价值与之和（这个论断可以通过画图的方式进行证明，目前似乎还没有找到更有说服力的纯文字证明）。因为我们最后择优输出，因此我们最终方案的总价值至少是最优方案的 $\frac{1}{2}$ 。

动态规划

背包问题的动态规划是老生常谈的问题了，时间复杂度是 $\mathcal O(nW)$ ，看起来是多项式？其实不然，因为有关的信息只需要 $\mathcal O(\log W)$ 个比特存储，因此这个时间复杂度实际上是和输入长度成指数级的。

多项式时间近似方案（PTAS）

接下来我们提供背包问题的一个多项式时间近似方案（PTAS）。什么是PTAS？一个PTAS可以认为是一类基于参数 $\varepsilon$ 的算法，且参数为 $\varepsilon$ 的算法构成问题的 $(1+\varepsilon)$ 倍近似（对于最大化问题则可以是 $(1-\varepsilon)$ 倍近似）。算法的运行时间可以和 $\frac{1}{\varepsilon}$ 成指数级（因为在每一个算法当中， $\varepsilon$ 被视作常数），如果算法的运行时间和 $1 \over \varepsilon$ 成多项式级，则这个PTAS被称为完全多项式时间近似方案（FPTAS或FPAS）。

要设计这个算法，我们先从DP入手。考虑背包问题的如下DP：设 A(i, p) 是考虑前个物品，总价值为时的最小总重，则有如下转移：

$A(i, p) = \begin{cases} 0, &i=0 \text{ or }p=0 \\ A(i-1, p), &p<p_i \\ \min \{A(i-1,p),w_i+A(i-1,p-p_i)\}, &\text{otherwise} \end{cases}$

如果设所有物品的最大价值是

，那么显然总价值最多便是

，DP的时间复杂度就是 $\mathcal O(n^2P)$ 。我们主要担心的问题是

太大，要解决这个问题，我们把

缩小就行了。

因此我们的PTAS是：对于每件物品，对其价格等比例缩小舍入，新的价格为 $p_i'=\lfloor p_i / k\rfloor$ 。随后进行DP，并输出DP的最优解。设最优解为。

这样一来我们的总价格是多少呢？（定义 $p(\cdot)$ 表示集合的价格）。

$\begin{aligned} p(S) &= \sum_{i \in S} p_i \\ &\ge \sum_{i \in S} p_i'k \\ &= k\sum_{i \in S} p_i' \\ &\ge k\sum_{i \in \mathrm{OPT}} p_i' \\ &\ge k\sum_{i \in \mathrm{OPT}} \left(\frac{p_i}{k} - 1\right) \\ &= \sum_{i \in \mathrm{OPT}} p_i- k|\mathrm{OPT}| \\ &\ge \sum_{i \in \mathrm{OPT}} p_i - kn \end{aligned}$

第二个不等号处用到了DP的最优性。

若令 $k=\frac{\varepsilon P}{n}$ ，则有

$\begin{aligned} p(S) &\ge \sum_{i \in \mathrm{OPT}} p_i - kn \\ &= \sum_{i \in \mathrm{OPT}} p_i - \varepsilon P \\ &\ge p(\mathrm{OPT}) - \varepsilon p(\mathrm{OPT}) \\ &= (1-\varepsilon) p(\mathrm{OPT}) \end{aligned}$

第二个不等号处用到了 $p(\mathrm{OPT}) \ge P$ 。（此处我们忽略不可能装得下的物品）

因此这个算法确实是一个PTAS。这个算法的运行时间是多少呢？

$\mathcal{O} (n^2P) = \mathcal O \left(n^2 \frac{P}{k}\right) = \mathcal O\left(\frac{n^3}{\varepsilon}\right)$

可见这个算法其实不仅是一个PTAS，还是一个FPTAS。这个时间复杂度可以说是很优秀的了。

PACT 07/05 我终于明白线性规划对偶是怎么回事了！

Posted on 2020-07-11

什么是线性规划？

线性规划，简单地来说就是在一系列线性约束下最优化一个线性函数的过程。

例如如下就是一个线性规划问题：

$\begin{aligned} \text{minimize}\quad &7x_1+4x_2+3x_3\\ \text{subject to}\quad &4x_1+2x_2-x_3\ge 50 \\ &2x_1+x_2+3x_3\ge 20 \\ &x_1,x_2,x_3 \ge 0 \end{aligned}$

这部分自己很早以前就会了。

在近似算法设计当中关于线性规划重要的一点是：它是可以在多项式时间内求得最优解的。具体的方法对于我们不重要，可以使椭圆形法或者其他内点法，反正只要知道可以就行了——我们就指望着它来帮助我们设计近似算法呢。

为什么要对偶？

对于一个最小化（最大化类似）的线性规划，我们问一个问题：

目标函数是否可以 $\le \alpha$ ？

答案如果是肯定的，这个问题有没有一个简短的肯定证明（Yes Certificate）？显然是有的：我们只要把一组目标函数是 $\alpha$ 的变量取值写出来，对方很快就可以验证我们的正确性。（“简短”与“很快”均指多项式空间与时间内，有简短肯定证明的问题被称为 $\mathsf{NP}$ 问题）

那答案如果是否定的呢？这个问题有没有一个简短的否定证明（No Certificate）？直觉上这就难了。（有简短否定证明的问题被称为 $\textsf{co-NP}$ 问题，它和 $\mathsf{NP}$ 的关系是至今计算机界悬而未决的）

幸好我们知道线性规划 $\in \mathsf{P}$ ，而 $\mathsf{P}\subseteq \textsf{NP} \cap \textsf{co-NP}$ 。也就是说确实是有否定回答的——是什么呢？（嘛，其实对于多项式时间算法，把算法的过程作为否定证明也可以算是“简短”的，因为一样的算法可以在多项式时间内验证它）

如果我们可以给目标函数一个 $>\alpha$ 的下界，不就证明目标函数不可能 $\le \alpha$ 了吗？

目标函数的下界是什么？

？这个下界太平凡了。

观察系数，因为 $x_1,x_2,x_3\ge 0$ ，而约束二式的各项系数都不大于目标函数的各项系数，因此

$\begin{aligned} 7x_1+4x_2+3x_3 \ge 4x_1+2x_2-x_3 \ge 50 \\ 7x_1+4x_2+3x_3 \ge 2x_1+x_2+3x_3 \ge 20 \\ \end{aligned}$

这个下界可以更好：

$7x_1+4x_2+3x_3 \ge (4x_1+2x_2-x_3)+(2x_1+x_2+3x_3) \ge 70$

或者更好？

$7x_1+4x_2+3x_3 \ge (4x_1+2x_2-x_3)+\frac{4}{3}(2x_1+x_2+3x_3) \ge \frac{230}{3}$

这样下去会不会没完没了？不妨设两个约束的系数是 $y_1,y_2\ge0$ ，那我们的下界就是

。

$\begin{aligned} 7x_1+4x_2+3x_3 &\ge y_1(4x_1+2x_2-x_3)+y_2(2x_1+x_2+3x_3) \\ &=(4y_1+2y_2)x_1+(2y_1+y_2)x_2+(-y_1+3y_2)x_3 \\ &\ge 50y_1+20y_2 \end{aligned}$

为了确保我们上面的推理没有问题，约束和的各项系数不应大于目标函数的各项系数，因此又有 $4y_1+2y_2\le 7$ ， $2y_1+y_2\le 4$ ， $-y_1+3y_2\le 3$ 。我们希望下界越紧越好，所以

要越大越好——我们想到了什么？另一个线性规划！

$\begin{aligned} \text{maximize}\quad &50y_1+20y_2\\ \text{subject to}\quad &4y_1+2y_2\le 7 \\ &2y_1+y_2\le 4 \\ &-y_1+3y_2\le 3 \\ &y_1,y_2\ge 0 \end{aligned}$

这就是所谓的“对偶线性规划”。如果我们给出一组

使得这个的目标函数 $>\alpha$ ，那么我们原来规划的目标函数就不可能 $\le \alpha$ ，即这就是我们所寻找的简短否定证明。

如果我们要求这个对偶规划的目标上界（也就是再对偶），不难发现我们又回到了最初的线性规划。

而由我们构造对偶规划的过程，不难明白为什么所有变量都要非负，为什么对偶问题的变量数等于原问题的约束数，约束数等于原问题的变量数，为什么最小化问题的约数要转化成 $\ge$ 的形式，最大化问题的约数要转化成 $\le$ 的形式，为什么对偶前后不等号方向会变化等问题。

一旦知道对偶的目的，这些步骤豁然开朗，而这些在大多教科书里是略过不讲的，或者先抛给你对偶的方式，再把这个目的冠以“弱对偶定理”的名号塞给你（此处点名《算法导论》），或许我们在阅读证明的时候能够明白这些步骤的用处，但是不免还是有些云里雾里。

但是严谨地走一遍还是必要的，此处给出线性规划对偶的定义：对于线性规划

$\begin{aligned} \text{minimize}\quad &\sum_{j=1}^nc_jx_j\\ \text{subject to}\quad &\sum_{j=1}^na_{ij}x_j\ge b_i \quad \forall i =1,2,\cdots,m \\ &x_1, x_2, \cdots, x_n\ge0 \end{aligned}$

其对偶线性规划（Dual）为

$\begin{aligned} \text{maximize}\quad &\sum_{i=1}^mb_iy_i\\ \text{subject to}\quad &\sum_{i=1}^ma_{ij}y_i\le c_j \quad \forall j =1,2,\cdots,n \\ &y_1, y_2, \cdots, y_m\ge0 \end{aligned}$

此时一开始的线性规划被称为主线性规划（Primal）。反之亦然。

所谓弱对偶原理

$\sum_{j=1}^nc_jx_j \ge\sum_{i=1}^mb_iy_i$

的证明：

$\begin{aligned} \sum_{j=1}^nc_jx_j &\ge \sum_{j=1}^n\left(\sum_{i=1}^ma_{ij}y_i\right)x_j \\ &= \sum_{i=1}^m\left(\sum_{j=1}^na_{ij}x_j\right)y_i \\ &\ge \sum_{i=1}^m b_iy_i \end{aligned}$

这其实就是我们之前例子中论述的严谨版本，注意到两个不等号之所以成立，不仅仅是因为 $\sum_{i=1}^ma_{ij}y_i \le c_j$ 以及 $\sum_{j=1}^na_{ij}x_j\ge b_i$ ，还有 $x_j\ge 0$ 和 $y_i\ge 0$ ，因此变量必须是非负的。

除此以外，更强的一个结论被称为强对偶原理：对偶规划与主规划的最优解相等。证明参见《算法导论》，在近似算法设计中，弱对偶原理才是最重要的。

互补松弛条件

令 $(x_1^*,x_2^*,\cdots,x_n^*)$ 与 $(y_1^*,y_2^*,\cdots,y_m^*)$ 为主线性规划和对偶线性规划的最优解，强对偶原理表明

$\sum_{j=1}^nc_jx_j^*=\sum_{i=1}^mb_iy_i^*$

回过头看我们弱对偶原理的证明过程，两个不等号必须同时取等，于是便得到两个条件，成为所谓的互补松弛条件（Complementary Slackness Condition）：

主互补松弛条件： x_j^*=0 或者 $\sum_{i=1}^ma_{ij}y_i = c_j$ ，即要么变量为，要么对偶规划里面的对应约束取等。

对偶互补松弛条件： y_i^*=0 或者 $\sum_{j=1}^na_{ij}x_j = b_i$ ，即要么变量为，要么主规划里面的对应约束取等。

评论测试

Posted on 2020-07-09

刚刚启用了博客的评论功能，基于Valine。本帖用于测试（如果后续更换评论系统，则依然使用本帖进行测试）

（真的会有人评论吗？）

PACT 07/04 浮账最大化（次模优化）

Posted on 2020-07-06 Edited on 2022-06-14

定义

在电子转账还未普及的年代，从付款人开出支票到钱从付款人账户里扣走之间是有一段等待的时间的，这段时间被称为浮账期（float time，网上似乎没有找到特别靠谱的翻译）。因为在浮账期这些付出去的钱还是能够产生利息的，人们自然希望这个浮账期越长越好。于是人们就抽象出了这么一个浮账最大化的问题。

输入：带权二分图 G=(V,E) ，其中 $V=B\cup P$ ，一侧是所有银行的集合，另一侧是所有交易的集合，第个银行到第个交易的边权为 $v_{ij}$ ，表示第个银行处理这笔交易所需的浮账时间。整数。

目标：选择家银行的集合 $S\subseteq B$ ，使得

$v(S) = \sum_{j\in P} \max_{i\in S}\{v_{ij}\}$

最大。

贪心算法

我们很容易想到如下的贪心算法：

一开始 $S=\emptyset$ 。
然后进行次循环，每次循环寻找能使目标函数增幅最大的银行加入。

简单，粗暴，好理解。

分析

引理1：令是第次循环开始时我们的银行集合，第次循环我们所选的新银行是 i_h ，那么有

$v(S\cup \{i_h\}) - v(S)\ge \frac{v(\mathrm{OPT})-v(S)}{k}$

即反映了一种“优于平均”的思想。（感觉类似的引理在贪心算法的分析当中经常会碰到）

要证明这个引理，我们需要引入第二个引理，或者说发掘 $v(\cdot)$ 的一个重要性质：

引理2（次模性）：对于任何 $X\subseteq Y\subset B$ 以及 $l\in B\setminus Y$ ，都有：

$v(X\cup \{l\}) - v(X) \ge v(Y\cup \{l\}) - v(Y)$

直观理解：随着集合变大，加入新元素的边际效应递减。

证明：

考虑对于固定的交易，在 v(X) 当中的贡献是 $\max_{i\in X}\{v_{ij}\}$ ，在 v(Y) 当中的贡献是 $\max_{i\in Y}\{v_{ij}\}$ ，而因为 $X\subseteq Y$ ，显然有

$\max_{i\in X}\{v_{ij}\} \le \max_{i\in Y}\{v_{ij}\}$

将

加入集合之后， $v_{lj}$ 加入了比较，有三种情况：

$v_{lj} \le \max_{i\in X}\{v_{ij}\}$ ，那么还是都不会增加。
$\max_{i\in X}\{v_{ij}\} < v_{lj} \le \max_{i\in Y}\{v_{ij}\}$ ，那么这边增加了，而这边不增加。
$v_{lj} > \max_{i\in Y}\{v_{ij}\}$ ，两边的最大值都增加了，但是增加幅度这边要大于。

由此可见，对于一个固定的交易，新银行加入后，这一侧的增加量一定不少于这一侧的增加量。因此对于所有交易求和之后，必有

$v(X\cup \{l\}) - v(X) \ge v(Y\cup \{l\}) - v(Y)$

得证。

这个“边际效应递减”的性质有一个高端的名字：次模性（Submodularity）。

引理1的证明：令 $\mathrm{OPT}\setminus S = \{i_1,i_2,\cdots,i_p\}$ 。注意到显然有 $p\le |\mathrm{OPT}|=k$ 。

$\begin{aligned} v(\mathrm{OPT}) &\le v(\mathrm{OPT} \cup S) \\ &= v(S) + v(\mathrm{OPT} \cup S) - v(S) \\ &= v(S) + \sum_{j=1}^p \left(v\left(S\cup \{i_1,i_2,\cdots,i_j\}\right) - v\left(S\cup \{i_1,i_2,\cdots,i_{j-1}\}\right)\right) \end{aligned}$

那个求和式是一个非常精巧的叠缩。接下来我们运用引理2，令 $X=S,Y=S\cup \{i_1,i_2,\cdots,i_{j-1}\}$ ：

$\begin{aligned} v(\mathrm{OPT}) &\le v(S) + \sum_{j=1}^p \left(v\left(S\cup \{i_1,i_2,\cdots,i_j\}\right) - v\left(S\cup \{i_1,i_2,\cdots,i_{j-1}\}\right)\right) \\ &\le v(S) + \sum_{j=1}^p (v(S\cup\{i_j\}) - v(S)) \\ &\le v(S) + \sum_{j=1}^p (v(S\cup\{i_h\}) - v(S)) \\ &= v(S) + p(v(S\cup\{i_h\}) - v(S)) \\ &\le v(S) + k(v(S\cup\{i_h\}) - v(S)) \end{aligned}$

倒数第三步运用到了我们算法的贪心性质，即 $v(S\cup\{i_h\}) - v(S) \ge v(S\cup\{i_j\}) - v(S), \forall j$ 。接下来我们马上就可以得到引理：

$\begin{aligned} v(\mathrm{OPT}) &\le v(S) + k(v(S\cup\{i_h\}) - v(S)) \\ v(\mathrm{OPT}) - v(S) &\le k(v(S\cup\{i_h\}) - v(S)) \\ v(S\cup\{i_h\}) - v(S) &\ge \frac{v(\mathrm{OPT}) - v(S)}{k} \end{aligned}$

证毕。

接下来我们可以开始证明我们算法的近似比了：

定理：我们的算法是一个 $\left(1 - \frac{1}{e}\right)$ 倍近似算法。

证明：令 S_t 表示第次循环后我们所选的银行集合。

由引理可得

$v(S_k) - v(S_{k-1}) \ge \frac{v(\mathrm{OPT}) - v(S_{k-1})}{k} \Rightarrow v(S_k) \ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-1})$

因此

$\begin{aligned} v(S_k) &\ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-1}) \\ &\ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right) \left(\frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-2})\right)\\ &\cdots \\ &\ge \frac{v(\mathrm{OPT})}{k}\left(1+\left(1-\frac{1}{k}\right)+\cdots+\left(1-\frac{1}{k}\right)^{k-1}\right) + \left(1-\frac{1}{k}\right)^kv(S_0) \\ &= \frac{v(\mathrm{OPT})}{k}\left(1+\left(1-\frac{1}{k}\right)+\cdots+\left(1-\frac{1}{k}\right)^{k-1}\right) \\ &= \frac{v(\mathrm{OPT})}{k}\frac{1-\left(1-\frac{1}{k}\right)^k}{1/k} \\ &= v(\mathrm{OPT})\left(1-\left(1-\frac{1}{k}\right)^k \right) \\ &\le \left(1-\left(e^{-\frac{1}{k}}\right)^k \right) v(\mathrm{OPT}) \\ &= \left(1 - \frac{1}{e}\right)v(\mathrm{OPT}) \end{aligned}$

证毕。

其实分析我们的贪心算法，我们发现我们其实只利用了 $v(\cdot)$ 的次模性，而没有利用 $v(\cdot)$ 的具体形式或者题目的具体要求。而次模性足以证明引理1，引理1足以证明近似比。也就是说，我们这个贪心算法及其分析是可以被推广到其他的次模优化问题上的。因此，这个看起来很简单粗暴的贪心算法，其实真的是非常有意思！

计一次讨分失败

Posted on 2020-07-04

数学出分了，我最后一题分数被扣光。

我的答案是

而很显然参考答案是

嘛确实是不一样的。但是我的答案和参考答案是等价的啊！

最多形式不优美，怎落得如此下场？

大概是老师批high了没注意到吧，我想，然后加了老师微信，自信满满地去讨回我失去的6分。

事实证明我还是太天真了。

你期末分数多少啊？

哦，那是好学生啊，好学生看不出来？

哦豁？！

如果我没写“用《点到直线距离》一节里的知识”你还可以是对的？

承认了？

我说了用《点到直线距离》一节里的知识啊？你是不是没看题？

不老师，我的条件也是基于点到直线距离的思想的，只是有一个额外的条件罢了。

你这个额外的条件就是牵强附会！

我的额外条件和你的 $\delta$ 的功能是一样的啊……都是用于修正反例的特殊状况，何况我的主条件还是基于距离的。

你这个充要条件根本没办法用！

这就说不过去了，我觉得用这个条件虽卖相不佳，但是真论应用起来不会复杂多少。

$\delta$ 书里有你看到没有啊？你没有用 $\delta$ 就说明你的认知也就这个水平。如果你再坚持，你这方面的数学认知就到顶了，不会再有进步了！

好，没想到 $\delta$ 是我的疏忽，但是我很好奇就凭寥寥数语和一道试题如何可以评判认知水平的？

先入为主的自信与居高临下的傲慢。

你是个好学生，数学追求完美的，因此你要学会去仔细品味正确答案……

又是好学生，我就不理解了你用这个先入为主的标签作甚？反衬？

数学追求完美还用你教？我承认我的答案形式上没有正解优雅，但是这无损其正确性！

我究竟是被高看了还是低看了？

分我是不会给的。还有问题吗？

我明白了。参考答案的简洁确实令人惊叹，谢谢老师。

诶，我究竟是讨分的还是去挨骂的？

老师你要是就事论事说我的答案和预设的方向不对我也就算了，毕竟应试考试难免这样。

你还点评起我的认知和能力来了？

你要是教了我两年就算了，还是在你我只说了几句话的情况下？

是不是每一个眼高手低的教师都有这种自认为见得多了的那种倨傲？我还真是见识了！

附加条件就是有问题，啊？

“追求完美”哈？

你倒是仔细数数从初中到高中有哪些判断的附加条件要加上一句 $\Delta > 0$ ？那个时候不加附加条件算错，现在加了你又不高兴了？或者说没把附加条件并到 d_1d_2 变成 $\delta_1\delta_2$ 你就不高兴了？

解析几何里面很多结论要存在算不算附加条件？算不算不完美？与之相比是不是向量要好得多，倾斜角要好得多，极坐标要好得多？我们是不是要全员追求完美抛弃有缺陷的斜率？

“用到点到直线距离这一节”哈？

$\delta$ 是这一节的内容，点到直线的距离就不是了吗？

都写了“试写出”了还整唯一标准答案？

我的答案和你的完全等价诶！

证明的思路也和你的大同小异诶！

就这样把所有分扣光？

我的结论好歹是对的，是不是应该和那些结论都是错的做一点区分？

就这样把一个90分以上黜落到90分一下？

很遗憾，虽然我理解了老师的理论（这无疑是一种可悲），但是从老师对我的态度我只能读出一种面对完全不认识的学生，一种不知何起的居高临下的自负与倨傲。

题目和答案都不错，我回去会好好欣赏的。

但这个老师就算了，我很庆幸高中前两年不是他教。

诶，自己真蠢，刚做题的时候天真地想期末大考能出出开放性探究题，讨分的时候天真地想老师或许只是疏忽而已。

到最后自讨没趣，只能在一个网络上无人问津的角落，乱发一通牢骚。

PACT 07/03 集合覆盖问题

Posted on 2020-07-04

集合覆盖问题

定义

输入：全集 $\mathcal{U}$ ，以及一些集合的集合 $S=\{S_1,S_2,S_3,\cdots,S_n\}$ ，满足 $\forall i, S_i\subseteq \mathcal{U}$ 。

目标：从中选择一个最小数目的集合，使得它们能够覆盖 $\mathcal{U}$ 中所有的元素（即并集为 $\mathcal U$ ）

如图， S_1,S_2,S_4 就构成一个集合覆盖。

贪心算法及其分析

我们的想法很简单：每次都取含有最多未覆盖元素的集合加入我们的覆盖集，不断循环直至所有集合都被覆盖。

我们定义 $\mathcal U_i$ 表示第次循环开始时未覆盖的元素集合，定义 S_i 表示第次循环选择的集合，假设我们选了个集合。有引理：

引理：

$\left|S_i \cap\mathcal{U}_i \right| \ge \frac{\left|\mathcal{U}_i\right|}{|\mathrm{OPT}|}$

这个引理其实反映了一个“优于平均”的思想。

证明：

$\begin{aligned} \left|\mathcal{U}_i\right| &= \left|\bigcup_{Z\in\mathrm{OPT}}\left(Z\cap\mathcal{U}_i\right)\right| \\ &\le \sum_{Z\in\mathrm{OPT}}\left|Z\cap\mathcal{U}_i\right| \\ &\le \sum_{Z\in\mathrm{OPT}}\left|S_i\cap\mathcal{U}_i \right| \\ &= |\mathrm{OPT}||S_i\cap\mathcal{U}_i | \end{aligned}$

得证。

定理：我们的算法是一个 $\mathcal{O}\left(\log n\right)$ 倍近似算法。

证明：考虑每次循环开始时未覆盖元素的数量：

$\begin{aligned} |\mathcal U_1| &= n \\ |\mathcal U_2| &= |\mathcal U_1| - |S_1\cap\mathcal{U}_1| \\ &\le |\mathcal U_1|\left(1-\frac{1}{|\mathrm{OPT}|}\right) \\ |\mathcal U_3| &= |\mathcal U_2| - |S_2\cap\mathcal{U}_2| \\ &\le |\mathcal U_2|\left(1-\frac{1}{|\mathrm{OPT}|}\right) \\ &\le |\mathcal U_1|\left(1-\frac{1}{|\mathrm{OPT}|}\right)^2 \\ &\vdots \\ |\mathcal U_k| &\le |\mathcal U_1|\left(1-\frac{1}{|\mathrm{OPT}|}\right)^{k-1} \\ &= n\left(1-\frac{1}{|\mathrm{OPT}|}\right)^{k-1} \end{aligned}$

因为 $\mathcal{U}_k\neq \emptyset$ ，有

$\begin{aligned} 1\le |\mathcal U_k| &\le n\left(1-\frac{1}{|\mathrm{OPT}|}\right)^{k-1} \\ 1\le n\left(1-\frac{1}{|\mathrm{OPT}|}\right)^k &\le n\left(e^{-\frac{1}{|\mathrm{OPT}|}}\right)^{k-1} \\ e^{-\frac{k-1}{|\mathrm{OPT}|}} &\ge \frac{1}{n} \\ -\frac{k-1}{|\mathrm{OPT}|} &\ge -\ln n \\ k &\le \ln n\cdot |\mathrm{OPT}|+1 \\ k &\le \mathcal O\left(\log n\right)|\mathrm{OPT}| \end{aligned}$

证毕。

跑满上界的输入样例

对于这个算法而言我们的分析能不能更好一点呢？这里有一个可以让满足这个上界的例子：

最优解显然是个集合，但是我们的贪心算法每一次都可能选到红色的集合，而这样就需要 $\mathcal{O}\left(\log n\right)$ 个集合完成覆盖了。

带权集合覆盖问题

如果把给每个集合赋予一个权重，而我们需要寻找一个权重和最小的覆盖集呢？这个问题被称作带权集合覆盖。

贪心算法及其分析

我们依然贪心，这个时候我们每次选择“性价比”最优的集合加入我们的覆盖集，设一个集合的权重为 $w(\cdot)$ ，那么我们每一次循环都挑选 $\frac{w(\cdot)}{|\cdot|}$ 最小的集合（ $|\cdot|$ 这里不算已经被覆盖的元素）。

如何分析这个算法？沿用分析不带权覆盖的记号，我们有引理：

引理：

$\frac{w(S_i)}{|S_i\cap \mathcal{U}_i|} \le \frac{w(\mathrm{OPT})}{|\mathcal{U}_i|}$

证明：

$\begin{aligned} \left|\mathcal{U}_i\right| &= \left|\bigcup_{Z\in\mathrm{OPT}}\left(Z\cap\mathcal{U}_i\right)\right| \\ &\le \sum_{Z\in\mathrm{OPT}}\left|Z\cap\mathcal{U}_i\right| \end{aligned}$

而由我们算法贪心的本质可知，

$\frac{w(S_i)}{|S_i \cap \mathcal{U}_i|} \le \frac{w(Z)}{|Z \cap \mathcal{U}_i|}, \quad \forall Z\in\mathrm{OPT}, Z\cap\mathcal{U}_i\neq\emptyset$

也就是

$|Z \cap \mathcal{U}_i| \le \frac{w(Z)}{w(S_i)}|S_i \cap \mathcal{U}_i|,\quad \forall Z\in\mathrm{OPT}, Z\cap\mathcal{U}_i\neq\emptyset$

因此

$\begin{aligned} \left|\mathcal{U}_i\right| &\le \sum_{Z\in\mathrm{OPT}}\left|Z\cap\mathcal{U}_i\right| \\ &\le \sum_{Z\in\mathrm{OPT}}\frac{w(Z)}{w(S_i)}|S_i \cap \mathcal{U}_i| \\ &= \frac{|S_i \cap \mathcal{U}_i|}{w(S_i)}\sum_{Z\in\mathrm{OPT}}w(Z) \\ &= \frac{|S_i \cap \mathcal{U}_i|}{w(S_i)}w(\mathrm{OPT}) \end{aligned}$

随后稍加变形便得引理，证毕。

定理：我们的算法是一个 $\mathcal O\left(\log n\right)$ 倍近似算法。

证明：

$\begin{aligned} |\mathcal U_1| &= n \\ |\mathcal U_2| &= |\mathcal U_1| - |S_1\cap\mathcal{U}_1| \\ &\le |\mathcal U_1|\left(1-\frac{w(S_1)}{w(\mathrm{OPT})}\right) \\ &\le |\mathcal U_1|\exp\left(-\frac{w(S_1)}{w(\mathrm{OPT})}\right)\\ |\mathcal U_3| &= |\mathcal U_2| - |S_2\cap\mathcal{U}_2| \\ &\le |\mathcal U_2|\exp\left(-\frac{w(S_2)}{w(\mathrm{OPT})}\right) \\ &\le |\mathcal U_1|\exp\left(-\frac{w(S_1)+w(S_2)}{w(\mathrm{OPT})}\right) \\ &\vdots \\ |\mathcal U_k| &\le |\mathcal U_1|\exp\left(-\frac{\sum_{i=1}^{k-1}w(S_i)}{w(\mathrm{OPT})}\right) \\ &= n\exp\left(-\frac{\sum_{i=1}^{k-1}w(S_i)}{w(\mathrm{OPT})}\right) \end{aligned}$

又因 $|\mathcal U_k| \ge 1$ ：

$\begin{aligned} n\exp\left(-\frac{\sum_{i=1}^{k-1}w(S_i)}{w(\mathrm{OPT})}\right) &\ge 1 \\ -\frac{\sum_{i=1}^{k-1}w(S_i)}{w(\mathrm{OPT})} &\ge -\ln n \\ \sum_{i=1}^{k-1}w(S_i) &\le \ln n\cdot w(\mathrm{OPT}) \end{aligned}$

证完了？还没有！我们的覆盖集的总代价是 $\sum_{i=1}^k w(S_i)$ ，还差一个

没有处理呢！

但是注意到之前的结论：

$\frac{w(S_i)}{|S_i\cap \mathcal{U}_i|} \le \frac{w(\mathrm{OPT})}{|\mathcal{U}_i|}$

而当

时因为是最后一轮，自然有 $|S_k\cap \mathcal{U}_k| = |\mathcal{U}_k|$ ，因此便有

$w(S_k) \le w(\mathrm{OPT})$

和之前的式子相加：

$\begin{aligned} \sum_{i=1}^{k-1}w(S_i) + w(S_k) &\le \ln n\cdot w(\mathrm{OPT}) + w(\mathrm{OPT})\\ \sum_{i=1}^{k}w(S_i) &\le (\ln n +1)w(\mathrm{OPT}) \\ \sum_{i=1}^{k}w(S_i) &\le \mathcal O(\log n) w(\mathrm{OPT}) \end{aligned}$

证毕。

其实，如果我们不知道如何给 w(S_k) 定界也没有关系。参考中心问题时我们使用的技巧，我们可以枚举尝试 $\mathrm{OPT}$ 当中权值最大的集合。

显然如果我们知道 $\mathrm{OPT}$ 当中权值最大的集合是什么，我们就会把权值大于这个集合的其他集合全部丢掉。这个时候我们算法的 w(S_k) 自然就不大于 $w(\mathrm{OPT})$ 了。

但是我们怎么知道我们猜的对不对呢？对不对不重要，重要的是因为我们尝试了每一个集合，我们至少会猜对一次——而对于猜对的那一次，我们的分析全部成立，我们的代价一定是不大于 $\mathcal O(\log n) w(\mathrm{OPT})$ 的。因此，如果我们最后取所有尝试的最小值作为我们的解，我们的最终代价一定也是不大于 $\mathcal O(\log n) w(\mathrm{OPT})$ （虽然最终代价未必是猜对的那一次的代价），我们的算法依然有效，而时间复杂度不过是多了一个而已。

这个技巧是很有意思的：如果可能性是多项式种，那么在只关注是否是多项式时间的近似算法当中，枚举一遍不失为一种好的思路。

另外一种分析方法

令 $e_1,e_2,e_3,\cdots,e_n$ 表示第 $1,2,3,\cdots,n$ 个被覆盖的元素（我们一次选的集合很可能一次性覆盖好几个元素，在这种情况下这些元素的排列可以任意）。我们接下来把集合的权重分摊到元素上，对于被集合 S_y 覆盖的元素 e_i ，定义其代价为

$\operatorname{price}(e_i) = \frac{w(S_y)}{|S_y \cap \mathcal{U}_y|}$

很显然，因为覆盖到

的时候

后面的元素一定没有覆盖到，因此 $|S_y \cap \mathcal{U}_y| \ge n-i+1$ 。因此

$\operatorname{price}(e_i) \le \frac{w(S_y)}{n-i+1}$

又由之前的引理以及 $|S_y \cap \mathcal U_y| \le |\mathcal U_y|$ ，可得 $w(S_y) \le w(\mathrm{OPT})$ ，因此

$\operatorname{price}(e_i) \le \frac{w(\mathrm{OPT})}{n-i+1}$

而我们的覆盖集的总代价为

$\begin{aligned} \sum_{i=1}^n w(S_i) &= \sum_{i=1}^n \operatorname{price}(e_i) \\ &\le \sum_{i=1}^n \frac{w(\mathrm{OPT})}{n-i+1} \\ &= w(\mathrm{OPT})\sum_{i=1}^n \frac{1}{n-i+1} \\ &= w(\mathrm{OPT})\sum_{i=1}^n \frac{1}{i} \\ &= w(\mathrm{OPT}) H_n \\ &= O(\log n) w(\mathrm{OPT}) \end{aligned}$

跑满上界的输入样例

有一个大集合，包含所有元素，权值为 $1+\varepsilon$ 。

还有个只包含一个元素的小集合，权值为 $\frac{1}{n}, \frac{1}{n-1}, \frac{1}{n-2},\cdots$ 。

对于这个输入，我们的贪心算法会把所有小集合选掉，总权重为 $H_n = \mathcal{O}(\log n )$ 。而最优解为那个大集合，总权重为 $1+\varepsilon$ ，二者差 $\mathcal{O}(\log n )$ 倍，和我们的分析一致，这也说明如果算法不变，我们没办法单纯通过分析得出更好的结果了。

其实集合覆盖问题可以证明hardness就是 $\mathcal{O}(\log n )$ 的，只是这个证明不简单，上课的时候只是顺带提了一下。

PACT 07/02 TSP问题

Posted on 2020-07-04

定义

输入：完全图 G=(V,E) ，边带正权，满足三角不等式。

目标：构造一个周游所有顶点的最小权回路。

下界估计

$\mathrm{OPT}$ 的下界是什么？

Hasit: $\mathrm{OPT} \ge n\cdot\min_{e \in E}\{w_e\}$

这确实是一个下界，但是太松了一点？

Andrew T: $\mathrm{OPT} \ge$ 边权最小的条边

好一点了，但是还不够！

我: $\mathrm{OPT}\ge$ 每个顶点相邻的最小边权

似乎还不够？

Mona: $\mathrm{OPT}\ge$ 最小生成树边权和

没错！证明这个并不难，回路首先是一个连通子图，而连通子图中边数最小的当属生成树，而生成树边权和最小的是最小生成树，因此最小生成树的边权和是一张图中所有连通子图边权和的下界。

基础近似算法以及分析

这启发我们先去构造的最小生成树：

如何在其基础上构造回路呢？

我们不妨给每一条边复制一份：

让后我们走一次DFS，下来的时候走黑边，上去的时候走绿边，整个回路的边权就是最小生成树边权的两倍。

但是这样的话很多点我们重复走了，因此实际走的时候如果接下来的几个点已经走过了我们就直接跳过，如图，数字表示访问顺序：

（不难发现，节点的访问顺序就是DFS序）

由于三角不等式的存在，这个回路的边权一定小于最小生成树边权的两倍。

由于 $\mathrm{OPT}\ge$ 最小生成树边权，因此这个算法至少是一个倍近似算法。

Christofides算法

我们为什么要把最小生成树上的每一条边复制一下？我们的目的其实是让最小生成树变为一张欧拉图。有了欧拉图之后就可以求出欧拉回路，有了欧拉回路之后就可以通过跳过重复点抄近道（shortcutting）的方式得到哈密尔顿回路，也就是我们近似算法的解。

由此可见，一开始的欧拉图很重要。最小生成树之所以不是欧拉图，是因为里面可能会有奇度数的点，那么只要把奇度数的点变成偶度数不就行了嘛！我们之前把每条边都复制一下那无论度数奇偶都变成偶度数了，未免太粗暴了一点。

如何把奇度数变成偶度数呢？首先很显然奇度数的点只有偶数个（度数之和必须是偶数），因此我们想到可以把这些奇度数的点两两配对——或者用更专业的术语来讲，在这些奇度数点的导出子图上计算一个最小权完美匹配。我们知道一个偶数点图的最小权完美匹配是可以通过带花树算法（Blossom algorithm）在多项式时间内求出的，所以这个思路没有问题。

现在我们有了一张欧拉图，只要求出欧拉回路然后在上面抄近道我们就得到了一条周游路线了。

这个算法被称为Christofides算法。

Christofides算法分析

如何分析这个最小权匹配的代价呢？

我们不妨考虑最优周游路线，以及在这条路线上的最小生成树的奇度数点：

如果定义连接奇度数点的橘色环的代价是，显然由三角不等式有 $C\le \mathrm{OPT}$ ，而如果我们把这个环拆开，便会得到两个完美匹配：

假设两个完美匹配的代价为 C_1,C_2 ，我们最小权匹配的代价为 $C^{\ast}$ ，显然有

$C=C_1+C_2\ge C^{\ast} + C^{\ast} = 2C^{\ast}$

因此可得

$C^{\ast} \le \frac{1}{2}\mathrm{OPT}$

同时我们知道最小生成树的代价 $\le \mathrm{OPT}$ ，因此整张欧拉图的代价 $\le \frac{3}{2}\mathrm{OPT}$ ，而抄近路得到的最终回路的代价只会更小，因此这是一个 $\frac{3}{2}$ 倍近似算法。

令人绝望的一般TSP问题

引理：对于没有三角不等式的一般TSP问题，除非 $\mathsf{P}=\mathsf{NP}$ ，不存在任何倍近似算法以及更优的近似。

证明：我们使用gap reduction来证明这一点。考虑哈密尔顿回路问题到TSP的规约。

哈密尔顿回路问题：给定图 G=(V,E) ，问是否存在哈密尔顿回路？

一般TSP问题：给定边带权完全图 G'=(V',E') ，计算最小权回路。

如何规约？对于中有的边，令其在中的权值为；对于中没有的边，令其在中的权值为 n+2 。

如此一来，如果存在哈密尔顿回路，则TSP解的代价为，反之则TSP的回路必定会至少用到一条中不存在的边，因此代价至少为 (n-1) + (n+2) = 2n+1 。

假设有一个TSP的倍近似算法，那么如果存在哈密尔顿回路这个算法只能输出，因为到 2n+1 中间有很大的gap，而如果不存在哈密尔顿回路，算法就会输出至少是 2n+1 的代价——因此，我们可以使用这个算法在多项式时间内解决NPC的哈密尔顿回路问题！而如果 $\mathsf{P} \neq \mathsf{NP}$ ，这是不可能的，因此不存在这样的算法。

绝望吧？

更绝望的事情是因为没有三角不等式我们的边权可以设得任意大，不止是 n+2 ，还可以是 3n+2 ， kn+2 ……我们可以用以上的论证在假定 $\mathsf{P} \neq \mathsf{NP}$ 的前提下否决任意近似比的近似算法——也就是这个问题根本无从近似。

PACT 07/01 任务调度问题

Posted on 2020-07-04

定义

输入：个任务，第个任务的运行时间为 p_i ，共有个相同的机器（一个任务在每台机器上运行时间都相同）。每台机器同一时间只能运行一个任务，每个任务只能在一台机器上运行（不能拆分）。

目标：合理地调度任务，使得完成所有任务的时间（makespan）最短。

下界估计

自然而然地，我们首先思考 $\mathrm{OPT}$ 的下界。一个比较容易想到的下界是耗时最长的任务所需要的时间：

$\mathrm{OPT} \ge \max_{i} \{p_i\}$

除此以外，考虑如果可以拆分任务，最短的运行时间是多少？自然是 $\frac{\sum_i p_i}{m}$ ，而这在现实中常常是做不到的，因此有：

$\mathrm{OPT} \ge \frac{\sum_i p_i}{m}$

这两个下界对于之后的算法分析非常有用。

算法

将所有的任务随机排成一列。
当一台机器完成了一个任务变得闲置了，马上把列表上的下一项任务安排到这个机器上去执行。
重复步骤2直至所有任务都被执行完毕。

这个算法是非常简单且自然的。

分析

我们算法给出结果的什么？自然是最后一个结束的任务的结束时间。如果我们设最后一个结束的任务为任务，且这个任务开始于 s_l ，那么就有：

$\mathrm{Cost} = s_l+p_l$

接下来我们进行放缩。

考虑 s_l 的上界是什么？

很显然，在时刻，除了即将运行的那台机器，其他机器上必须有任务在运行或者刚刚空下来（如果有机器已经空了一阵子了，那当时就会被安排到那台机器上去跑），因此不难得出 $ms_l \le \sum_{i\neq l} p_i$ ，即

$s_l \le \frac{\sum_{i \neq l}p_i}{m}$

因此

$\begin{aligned} \mathrm{Cost} &= s_l+p_l \\ & \le \frac{\sum_{i \neq l}p_i}{m} + p_l \\ &= \frac{\sum_{i}p_i}{m} + \left(1 - \frac{1}{m}\right) p_l \\ &\le \frac{\sum_{i}p_i}{m} + \left(1 - \frac{1}{m}\right)\max_{i}\{p_i\} \\ &\le \mathrm{OPT} + \left(1 - \frac{1}{m}\right)\mathrm{OPT} \\ &= \left(2 - \frac{1}{m}\right)\mathrm{OPT} \end{aligned}$

我们就证明了我们的算法是一个

倍近似算法！

提升近似比

能不能在这个算法的基础上提升呢？我们注意到将 $\mathrm{OPT}$ 作为 p_l 的上界其实还是太松了。如果我们能够缩短 p_l ，那上界的估计有没有改善的空间呢？

于是我们在原来算法的基础上不妨进行一个改进：与其在一开始将所有任务随机排列，不如将其按照运行时间从大到小的顺序进行排序。这也很符合直觉，一开始就把需要时间很长的任务跑完，之后肯定有些机器空着有些机器还在忙，这个时候就可以用完成时间比较短的小任务来灵活地填补这些空缺了。

这一下让近似比提升了多少呢？

引理：加上排序之后的算法具有 $\frac{3}{2}$ 的近似比。

证明：我们不妨分类讨论，

情形1. $p_l \le \frac{1}{2}\mathrm{OPT}$ ，这个时候按照我们上文分析的路子走直接就可以得到 $\mathrm{Cost} \le \frac{3}{2}\mathrm{OPT}$ ，就做完了。

情形2. $p_l > \frac{1}{2}\mathrm{OPT}$ ，此时所有之前的任务也肯定具有大于 $\frac{1}{2} \mathrm{OPT}$ 的运行时间。注意到我们不需要考虑之后的任务，因为依据定义是最后结束的，后面的任务对于我们的结果没有影响。那之前的任务在最优调度里面是怎么样的呢？反证法可以很快说明：在最优调度里面，每一台机器至多只能处理一件任务（忽略之后的任务）！也就是说事实上以及之前的任务数目加起来不会超过机器数，那再想一想在这种机器充足的情况下，我们的算法在分配这些任务的时候也是一个机器一个任务， p_l 必定是从一开始就执行的，因此 $\mathrm{Cost}=p_l$ ，而显然 $\mathrm{OPT} \ge p_l$ ，因此必有 $\mathrm{Cost} = \mathrm{OPT}$ ，结束。（事实上，由于还是最后结束的任务，不难想通在一机器一任务的情形下，之前的所有任务都一定和花费相同的时间，或就是我们算法分配的第一个任务。）

综上所述，近似比是 $\frac{3}{2}$ 。

进一步提升近似比

通过对于上述论证的些许修改，我们其实可以证明：

引理：加上排序之后的算法具有 $\frac{4}{3}$ 的近似比。

证明：我们故技重施：

情形1. $p_l \le \frac{1}{3}\mathrm{OPT}$ ，这个时候我们直接就可以得到 $\mathrm{Cost} \le \frac{4}{3}\mathrm{OPT}$ 。

情形2. $p_l > \frac{1}{3}\mathrm{OPT}$ ，此时所有之前的任务也肯定具有大于 $\frac{1}{3} \mathrm{OPT}$ 的运行时间。我们同样不考虑之后的任务。可以通过反证证明：在最优调度里，每一台机器至多只能处理两件任务！因此，我们确定有足够的机器让我们的算法得以这样调度任务：

（看着是不是很像双指针？）

具体来说，如果我们把机器按照第一个任务的耗时降序排序，那么它们第二个任务的耗时一定成升序排列。（这并不难证明：第一个任务耗时最短的机器一定能够先领到列表中最长的任务作为第二个任务，之后的机器领到的任务时间递减）

（在这里我们假定一定是第二个任务，如果从头开始运行而且时间特别长的话，参考上一节的证明）

而接下来我们证明这样的分配方式是最优的。

我们采取反证的方法：不妨假设在最优方案中存在两个机器，两个机器上都有两个任务，耗时分别为 (a,b) 和 (c,d) ，且 a>c,b>d 。那么我们把两个机器上的第二个任务互换，变成 (a,d) 和 (c,b) ，不难发现此时完成任务的最短时间会减少，和“最优”矛盾。因此，对于最优方案的任意两台机器 (a,b) 和 (c,d) ，如果 a>c 那么 b<d ：

这正是我们算法所给出的调度方案。因此 $\mathrm{OPT}$ 不会比我们算法的结果更好了。

综上所述，近似比为 $\frac{4}{3}$ 。

论省选中有意思的一道组合题

Posted on 2020-06-27

省选结束了，本人作为划水3年的OIer宣告原地退役，唯一写出正解的是D1T2。我其实觉得这道题挺有意思的（虽然大佬们都说只是推式子而已……嘛，毕竟本来没期待自己能做出来），就写篇文章记一下自己的想法吧。

题意

给定整数 $n, x, P\le 10^9$ ，以及一个 $m \le 1000$ 次整系数多项式，求

$\left[\sum_{k=0}^nf(k)x^k\binom{n}{k}\right]\bmod P$

心路历程

先乱搞一波

看到这个题目的第一眼我觉得颇为眼熟。虽然没学过奥数，印象当中《具体数学》里面花了很大笔墨讲由这种指数，多项式以及二项式系数组合而成的和式的处理方法，似乎最后也讲到了机械求和法，然并卵，印象止步于印象，机械求合法太复杂了自己并没有记下来。

但是自己的残存记忆告诉我机械求和法的第一步是把求和式化成超几何函数，虽然后者我更没办法但是本着有逼就要装的思想……为什么不试一试呢？

什么样的级数是超几何的？《具体数学》里面给出的方法是求相邻项之比~~幸好这个我还没有忘记~~，而显而易见地是多项式求比是求不出具有良好形式的结果的，因此多项式必须转化为性质更优良的下降阶乘幂处理（关于下降阶乘幂我记得两年之前就写过一篇成套方法和有限微积分的博文，现在想来下降阶乘幂在离散求和问题当中真的有非常良好的性质，我在这里就沿用《具体数学》里的记号了： $k^{\underline m} = \prod_{i=0}^m (k-i)$ ）：

$\begin{aligned} \frac{(k+1)^{\underline{m}}x^{k+1}\binom{n}{k+1}}{k^{\underline{m}}x^k\binom{n}{k}} &= \frac{(k+1)x(n-k)}{(k-m+1)(k+1)} \\ &= \frac{(n-k)x}{k-m+1} \end{aligned}$

不出所料，结果是一个有理函数，也就是说可以化成高斯超几何函数呢！

不出所料，半瓶水的某人也就知道这些了（悲）。

但是下降阶乘幂的思想是可以有的嘛！

部分分摸鱼

在乱搞如预想的那般失败之后我就开始看部分分。

部分分里面有一个是常数的，愣了一会发现能用二项式定理，答案是 (1+x)^n 。

然后还有一个 x=1 的。这个要怎么解决？

从最简单的一次多项式开始：

$\sum_{k=0}^nk\binom{n}{k}=?$

推式子本人是不会的，结论也忘了，但是从组合意义上还是好想的： $k\binom{n}{k}$ 就是从个人里面选个人，然后钦定一个做队长的方案数，把它求和，就是从个人里面选若干人，然后从当中钦定一个队长的方案数。这是先选人再定队长的顺序，我们可以先选队长再选人嘛！从

个人里面选一个队长有

种方法，剩下的

个人要不要都行，所以是 $2^{n-1}$ 种，二者相乘：

$\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$

就把一次的式子推出来了。

那二次的式子呢？

$\sum_{k=0}^nk^2\binom{n}{k}=?$

如果沿用之前运用组合意义化简的思路，那

就有“可以重复选”的含义在，是不好处理的。但是之前的乱搞告诉我们，是不是化成下降阶乘幂会好处理一点呢？

$\sum_{k=0}^nk(k-1)\binom{n}{k}=?$

答案是肯定的，思路和一次的完全一样，只是从“选队长”变成了“选队长和副队长“，因此很快就可以得出：

$\sum_{k=0}^nk(k-1)\binom{n}{k}=n(n-1)2^{n-2}$

然后就可以很快地推广出去了：

$\sum_{k=0}^nk^{\underline{m}}\binom{n}{k}=n^{\underline{m}}2^{n-m}$

这样几个部分分就基本拿到了。

把两者组合起来

那如果 $x\neq 1$ 且非常数要怎么做呢？我们不妨还是把想成下降阶乘幂（怎么拆另说）：

$\sum_{k=0}^nk^{\underline{m}}x^k\binom{n}{k}=?$

然后思考其组合意义，稍开脑洞即可得到：

$k^{\underline{m}}x^k\binom{n}{k}$ 是从个人里面挑选个人，再给让当中人担任个不同职位，最后再让每个人从种颜色的帽子当中选一个戴上的方案数（不要问我怎么想到戴帽子的）。

因此，由加法原理，对其求和之后就是从个人里面挑选若干个人，再给让当中人担任个不同职位，最后再让每个人从种颜色的帽子当中选一个戴上的方案数。

那我们故技重施，调换顺序，不妨先从个人当中调出担任个职位的那个人（ $n^{\underline{m}}$ 种取法），再先让他们先选帽子（ x^m 种选法），然后让剩下的 (n-m) 个人要不挑一个颜色的帽子进队要么滚蛋（ $(1+x)^{n-m}$ 种取法）。于是就有了：

$\sum_{k=0}^nk^{\underline{m}}x^k\binom{n}{k}=n^{\underline{m}}x^m(1+x)^{n-m}$

哇，式子就推出来了！

多项式拆分

现在基于下降阶乘幂的式子已经推出来了，唯一剩下的就是把给定的拆成若干个下降阶乘幂的线性组合。

$\sum_{i=0}^ma_ik^i = \sum_{j=0}^m b_jk^{\underline{j}}$

即求

的过程。

显而易见地，我们需要从高次到低次拆，这样后拆出来的幂才不会对之前的结果造成影响。

同时显然的是，我们需要知道下降阶乘幂展开后对应多项式的系数。

现在回过来看，朴素的多项式乘法是完全可以胜任的。但是写多项式乘法毕竟比较繁琐，不如观察多项式系数的规律。

令 c[m, n] 表示下降阶乘幂 $x^{\underline m}$ 的展开式当中 x^n 的系数。则由下降阶乘幂的定义：

$x^{\underline m} = x^{\underline{m-1}}[x-(m-1)],\quad (m\ge 1)$

可以得出递推式：

边界条件是

以及 $c[m,0]=0\quad \forall m>0$ 。这是一个类似杨辉三角的递推式，自然可以在 $\mathcal{O}\left(m^2\right)$ 的时间内算出来，代码也好写。

至此，这道题目就完全解决了。

其实不止如此，这个三角在考场上让我感到非常眼熟，回去查证了一下，果然 c[m,n] 就是所谓的带符号的第一类斯特林数，“下降阶乘幂的展开系数”正是其重要的性质之一。

感想

这道题对我的感触是比较深刻的，尤其是做出来之后，颇有一种成就感。

细想来，我组合数学的公式其实几乎都没有背过，故而几乎所有的式子都是现场推出来的。而且推理的方式也不纯代数的暴算，而是通过combinatorial proof的方式。自从PACT学来这招之后我觉得这种方法实在是精妙。在最后自己还稀里糊涂地推演出了斯特林数的递推公式，或许这种高大上的组合数本身离我们就不遥远吧。

而话又说回来，大佬们看我写的这篇文章，只怕有些不耐烦与乏味吧。那些认真学习过组合数学的选手，大概看到这道题只剩下满满的套路，毕竟斯特林数名声在外，falling factorial这个套路熟悉了也不难想到，而类似的组合式子大概课后的习题会有很多吧。看到诸多大佬将D1T2云淡风轻地说成“裸的推式子”，他们做这道题时的从容大概可见一斑。只有像自己这样偶尔翻翻《组合数学》和《具体数学》，半瓶水晃荡的，才会在考场上各种心情复杂，一惊一乍了。

然而换一个角度，我觉得这道题对我来说真的不错，自己之前偶尔翻翻书也是。作为一道数学题，这道题并没有远远超出我的见识让我一筹莫展，也没有远远低于我的见识让我秒杀，恰是我稍微努力一下就能解决的。而这次考试正是给了日渐颓废，游手好闲的我一个“努力一下”的契机。就结果来看，解决这道题不仅给了我市选的信心，也给了我组合数学的信心，还让我在结题过程中观赏到了极佳的风景，似乎确实不赖。尤其是后者，若放在平时做题，随时可以查找资料，正确答案触手可及，那结论得出时大概也不会有考场上那么惊喜，那么愉悦了。

逆转

啊？出分了？！

我考个250都能压线进队？！

我可是根本就没认真复习啊，半年没碰OI了……

唉，看来这次强行退役失败了，心情复杂……

概率论初步

期望的线性性

随机变量的方差

马尔科夫不等式

切比雪夫不等式

切尔诺夫上界（Chernoff Bound）

三个不等式给出上界的比较

近似算法初步

定义

例：最小顶点覆盖问题

线性规划舍入（LP Rounding）

背包问题

定义

贪心算法

动态规划

多项式时间近似方案（PTAS）

什么是线性规划？

为什么要对偶？

互补松弛条件

定义

贪心算法

分析

集合覆盖问题

定义

贪心算法及其分析

跑满上界的输入样例

带权集合覆盖问题

贪心算法及其分析

另外一种分析方法

跑满上界的输入样例

定义

下界估计

基础近似算法以及分析

Christofides算法

Christofides算法分析

令人绝望的一般TSP问题

定义

下界估计

算法

分析

提升近似比

进一步提升近似比

题意

心路历程

先乱搞一波

部分分摸鱼

把两者组合起来

多项式拆分

感想

逆 转

逆转