AOR3 近似算法

许多问题都可以用线性整数规划表示，但是极少数可以由线性规划直接求解。其中，大多数问题是NP-Hard的，所以近似算法是一种重要的求解方法。本节我们要介绍的就是LP Rounding Based近似算法。

概念引入

对于一个极小化问题，称一个实例为$I$，近似算法为$A$，则$A(I)$表示算法$A$的目标函数值，$OPT(I)$表示最优目标函数值。

近似比： 若对于任何实例，都有$A(I) \leq r * OPT(I), r \ge 1$，那么称$\rho = inf\{r\}$为近似比。

• 等价定义：$\rho = \sup{\frac{A(I)}{OPT(I)} }$
• 对于极大化问题，取$\rho = \sup{\frac{OPT(I)}{A(I)} }$。
• 所以一般地，我们有：$\rho = sup \{\frac{OPT(I)}{A(I)}, \frac{A(I)}{OPT(I)}\}$

近似比的确定： 往往我们无法求出$OPT(I)$，只能通过$OPT(I)$的范围来确定近似比。以极小化问题为例，确定近似比需要以下两个条件：

• 首先要满足对于任何实例，都有$A(I) \leq r * OPT(I), r \ge 1$。则r是近似比的下界。
  • 找到一个$OPT(I)$的下界$LB(I)$，使得$A(I) \leq r * LB(I)$。
• 要满足对任意 $\epsilon \ge 0$，存在 $I_{\epsilon}$，使得 $A(I_{\epsilon}) \ge (r - \epsilon) * OPT(I_{\epsilon})$。则r是近似比的上界。
  • 构造$I_{\epsilon}$

一些研究思路：

• Positive Result： 在P≠NP的假设下，设计近似比尽可能小（尽可能接近1）的近似算法。

  • PTAS：存在算法$A_{\epsilon}$，对任意$\epsilon \ge 0$，$I$，都有$A(I) \leq (1+\epsilon) * OPT(I)$，并且运行时间$O(I)=|I|^{O(f(\frac{1}{\epsilon}))}$
  • EPTAS：满足$A(I) \leq (1+\epsilon) * OPT(I)$，并且运行时间$O(I)=|I|^{O(1)}*f(\frac{1}{\epsilon})$
  • FPTAS：满足$A(I) \leq (1+\epsilon) * OPT(I)$，并且运行时间$O(I) = |I|^{O(1)}*(\frac{1}{\epsilon})^{O(1)}$

• Negative Result： 在P≠NP，NP≠ZPP等假设下，证明没有FPTAS/EPTAS/PTAS/$(r - \epsilon)$近似的算法。

LP-rounding based近似算法

整数间隙

在求解整数规划问题$IP$时，可以先进行条件的松弛。把整数约束$x \in Z^+$松弛为$x \ge 0$，得到分数线性规划的解$x^*_{LP}$，得到分数线性规划的目标函数值$C^*_{LP}$。

• 显然，$C^*_{LP} < C^*_{IP}$，该解是优于整数最优目标函数值$C^*_{IP}$的。

• 对$x^*_{LP}$做rounding得到$x_{IP}$，得到近似算法的目标函数值$C_{IP}$。

则近似比$\rho = \displaystyle\frac{C_{IP} }{C_{IP}^*} \le \displaystyle\frac{C_{IP} }{C_{LP}^*}$，所以$\displaystyle\frac{C_{IP} }{C_{LP}^*}$是近似比的上界，即rounding解目标函数值与分数解目标函数值的比。我们比较关心这个值，因为$\displaystyle\frac{C_{IP} }{C_{LP}^*}$比较小的时候，才有分析的意义。

又因为$\displaystyle\frac{C_{IP} }{C_{LP}^*} \ge \frac{C_{IP}^{*} }{C_{LP}^*}$，我们称$\displaystyle\frac{C_{IP}^{*} }{C_{LP}^*}$为整数间隙，即整数最优解和分数最优解的比值。它是$\displaystyle\frac{C_{IP} }{C_{LP}^*}$的一个下界，所以，整数间隙大，则无法得到有意义的分析。

背包问题

设共有 $n$ 件物品，$v_i$ 表示第 $i$ 件物品的价值，$w_i$ 表示第 $i$ 件物品的重量，$c$ 表示背包的最大承重，$x_i \in \{0, 1\}$ 表示是否选择第 $i$ 件物品。那么 0-1 背包问题可以写为 $\begin{matrix} \max\limits_x & \sum\limits_{i=1}^n v_ix_i \\ \text{s.t.} & \sum\limits_{i=1}^n w_ix_i \le c \\ & x_i \in \{0, 1\} \end{matrix}$

把整数要求松弛成 $x_i \ge 0, x_i \le 1$。

根据之前的知识，设$v_1/w_i \ge v_2/w_2 \ge \dots \ge v_n/w_n$。则LP的一个最优解为$(1, \dots, 1, \alpha, 0, \dots, 0)$。其中1有$k$个，$0 < \alpha \le 1$。则整数间隙Integrality Gap为2。

• 设前$k$个物品重量和为$W_1$，第$k+1$个物品重量$W_2$。则$2W_{IP}^* \ge W_1 + W_2 \ge W_{LP}^*$。所以$Gap =\frac{W_{LP}^*}{W_{IP}^*} \le 2$。
• 可以构造一个例子，一个物品重量，value分别为$(\frac{C}{2},C)$,另一个物品$(\frac{C+1}{2},C)$，这样$Gap =\frac{W_{LP}^*}{W_{IP}^*}=\frac{2C}{C+1}$，因此Gap至少2。

顶点覆盖问题

求所有顶点的一个权值最小子集，使得所有边的两个顶点，至少有一个顶点在这个子集内。$\begin{matrix} \min\limits_x & \sum\limits_{i=1}^n w_ix_i \\ \text{s.t.} & x_i + x_j \ge 1,\ \forall (i, j) \in E \\ & x_i \in \{0, 1\} \end{matrix}$

• LP rounding：对$x_i$的限制松弛为$x_i \ge 0$。

• 对偶问题：每个点有一定的权值，现在给所有边分配权值，使得与某个点相连的所有边的权值都不能超过点权值，如何分配使得所有边的权值和最大。

• 顶点覆盖问题的基本可行解是半整的，即$x_{i} \in \{0, 0.5, 1\}$

  • 假设存在一个基本可行解是非半整的，构造向量$V_{+}=\{i|\frac{1}{2} < x_{i} < 1 \}, V_{-}=\{i| 0 < x_{i} < \frac{1}{2} \}$，那么总能找到一个足够小的$\epsilon > 0$构造两个解$y=\{x_{i}+\epsilon(i \in V_{+}), x_{i}-\epsilon(i \in V_{-}),x_{i}\}$，$z=\{x_{i}-\epsilon(i \in V_{+}), x_{i}+\epsilon(i \in V_{-}),x_{i}\}$，可得$y,z$都是满足条件的可行解，且满足$x=(y+z)/2$，所以基本可行解一定是半整数解。

• 拓展：顶点覆盖问题的整数间隙为$2-\frac{2}{X^{f}(G)}$，$X^{f}(G)$表示对图$G$进行染色的最少颜色数。

Unrelated Machine Scheduling

问题描述: n个工件，m个机器，$p_{ij}$表示第$j$个工件在第$i$个机器上的运行时间，使得机器的最大负载（完工时间）最小。

模型：$x_{ij}$表示工件$j$是否安排给机器$i$，是的话取1，否则取0：$\begin{matrix} \min\limits_{x, t} & t \\ \text{s.t.} & \sum\limits_{i=1}^m x_{ij} = 1 & \forall j \in \{1, 2, \dots, n\} \\ & \sum\limits_{j=1}^n x_{ij}p_{ij} \le t & \forall i \in \{1, 2, \dots, m\} \\ & x_{ij} \in \{0, 1\} \end{matrix}$

• 不能直接进行 LP 松弛，因为那样的话工件可以任意拆分。假设只有一件物品需要加工，而且该物品在所有机器上的加工时间都为 1。那么原问题的最优目标函数值显然为 1，然而 LP 松弛后的最优目标函数值为 $1/m$（LP 松弛求出的最优解为 $x_{i, 1} = 1/m$），过于优秀，下界太松了，很难进行近似比分析。所以，直接做rounding得到的线性规划解没有参考价值。
• 改动：猜一个目标函数值$T$，二分 $T$ 的值。过程如下：如果 $p_{ij} > T$，就让 $x_{ij} = 0$ （或者直接把这个变量从 LP 中拿走）,看看之后的线性规划LP(T)是否可行。如果可行就减少$T$，不可行就增大$T$，这样二分得到。显然，让改动后的 LP 问题存在可行解的最小的 $T$，就是原问题最优目标函数值的下界（用两阶段法的第一阶段判断是否存在可行解即可）。这个求得的就是LP最优解。
• 如何rounding：给原来的LP加上约束：任何一个机器都不能执行它需要超过$T$才能完成的任务，即使它只负责这个任务的一部分，比如$p_{ij}>T$那么任务$j$一定不能在机器$i$上运行，这样更符合整数规划的实际要求，约束更紧。
• 现在一共有$n+m$个约束，对应的在基本可行解中最多有$n+m$个正分量（考虑入基出基解单纯性的过程），设被一个机器做完的任务有$n_{1}$个，被分开做完的有$n_{2}$个，可以得到$n_1 + n_2 = n$，$n_{1}+2*n_{2} \leq n+m$，因为分开至少分到两个机器上，就对应着答案中两个正分量。
• 所以$n_2 \le m$，最多有$m$个工件是拆分的。
• 由于我们限定了任何的$p_{ij} \leq T$，因此如果我们能把分开做的任务与机器一一匹配（上一行可知$n_{2} \leq m$）再做时间$T$，那么一定可以在$2T$内完成，这样就找到了一个整数解。这样的匹配一定存在吗？下面来构造这种匹配。
• 定义：若连通图中边数$\le$点数，即树再加一条边，那么称该连通图为伪树；若一张图的所有连通块都是伪树，那么称该图为伪森林。
• 构造一张二分图：左边有 $m$ 个点，每个点表示一台机器；右边有 $n$ 个点，每个点表示一件物品。若 $x_{i, j} > 0$ 则连接第 $i$ 台机器和第 $j$ 件物品。如果这个二分图不连通，那么对每个连通块分别求解，最后把解合并起来就是答案，所以我们假设该二分图连通。由于非零变量至多有 $n+m$ 个，所以该连通图的边数不超过点数，是一个伪树。
• 考虑“整数物品”。很显然，每个“整数物品” $j$ 都只和一台机器 $i$ 有连边 $(i, j)$，那就把“整数物品” $j$ 放在机器 $i$ 中加工，并去掉物品 $j$ 和边 $(i, j)$。由于每次恰好去除一个点和一条边，这张图仍然是伪树。根据前面我们加的约束，容易看出，每台机器对它所连工件的完整加工总时长也至多为 $T$。
• 考虑所有度数为 1 的机器 $i$。假设唯一连接机器 $i$ 的边是 $(i, j)$，那么我们把“分数物品” $j$ 放在机器 $i$ 中加工，并去掉机器 $i$、物品 $j$ 和物品 $j$ 的所有连边。由于每件“分数物品”都有至少两条连边（度数至少为 2），所以我们每次都会去掉两个点以及至少两条边，剩下的图是伪森林。考虑每个连通块就行。
• 反复考虑度数为 1 的机器并进行删除操作，直到最后不存在度数为 1 的机器为止。剩下的所有机器都度数为2，所有工件也度数为2，构成若干环。随便给每台机器分配一件物品即可。
• 这样，每台机器至多分配到一个“分数物品”，一件物品的加工时间至多为 $T$，再加上原来分配给它的“整数物品”，每台机器的总加工时长至多为 $2T$，整数间隙最大为$2$。

对偶近似算法

算法思路

• 考虑整数规划问题P：$\begin{aligned} \min & \sum c_{j}x_{j} \\ \text{s.t.} \ & \sum a_{ij}x_{i} \geq b_{i} \end{aligned}$松弛为线性规划要求$x_{j} \geq 0$。

• 那么它的对偶问题D就是$\begin{aligned} \max & \sum b_{i}y_{i} \\ \text{s.t.}\ & \sum a_{ij}y_{i} \leq c_{j} \\ & y_{i} \geq 0 \end{aligned}$。

• 回忆互补松弛条件，在$x,y$取最优解时满足$x_{j}=0$或$\sum a_{ij}y_{i} = c_{j}$，$y_{i}=0$或$\sum a_{ij}x_{j} = b_{i}$。但对于整数规划很有可能取不到等号。

• 思路：要求 $x_j$取整数，对上述条件进行放缩。即存在一组$\alpha, \beta \ge 1$使得：

  • $x_{j}=0$ 或 $\frac{c_{j} }{\alpha} \leq \sum a_{ij}y_{i} \leq c_{j}$。达不到$c_j$，但不会小太多。

  • $y_{i}=0$或$b_{i} \leq \sum a_{ij}x_{j} \leq \beta * b_{i}$。比$b_i$多一些，但不会多太多。

若x, y可行并满足上述条件，则： $\begin{aligned} & \sum c_{j}x_{j} \leq \alpha * \sum (\sum a_{ij}y_{i})x_{j} \\ = & \ \alpha * \sum (\sum a_{ij}x_{j}) y_{i} \\ \leq & \ \alpha * \beta * \sum b_{i}y_{i}\\ \leq & \ \alpha * \beta * OPT_{Dual} \\ \leq & \ \alpha \beta * OPT_{IP} \end{aligned}$

思路：确定尽可能小的$\alpha, \beta$使得构造的解尽可能满足互补松弛条件。

• 对于0-1整数规划，一般从$y$的可行解出发，$\alpha$或$\beta$取$1$逐步改进对偶解，得到原始整数解。

• 使用近似对偶算法的思路是从一组对偶问题的可行解出发，尝试调整对偶问题的可行解来找到原问题的最优解，如果能证明取到的一个$\alpha, \beta$满足上述式子，则可证明出这个算法是$\alpha\beta$近似的。

集合覆盖问题

集合覆盖问题：有若干集合$U \in 2^{E}$，寻找若干集合使得总费用最小并且保证$E$每个元素都被包含了至少一次，写为整数规划模型即 $\begin{aligned} \min \sum _{s\in U} c(s)x_{s} \\ \text{s.t. } \sum_{s:e \in s}x_{s} \geq 1 \\ x_{s} \in \{0, 1\} \end{aligned}$。

• 顶点覆盖问题也是一个集合覆盖问题。

松弛约束为$x_{s} \geq 0$，得到对偶问题 $\begin{aligned} \min & \sum_{e \in E}y_{e} \\ \text{s.t. } & \sum_{e\in s}y_{e} \leq c(s) \\ & y_{e} \geq 0 \end{aligned}$。

$f$近似算法：$f$是出现频次最高的元素出现的次数。首先有一个对偶可行解$y=0$，然后逐步提升$y_{e}$直到达到某个约束，如果满足了某个约束则称这个集合被选择了，$x_{s}=1$，然后将集合中的点移除集合。继续提升剩下的点集，注意此时不提升已经覆盖的元素的权值。这么做下去，直到所有元素被覆盖，这样我们就得到了一个原问题的解。

对这个算法，$x_s \ne 0\ \rightarrow x_s = 1 \ \rightarrow$ 这个集合被选中，对偶约束满足了 $\rightarrow \sum_{e\in s}y_{e} = c(s)$。所以$\alpha = 1$。

而 $y_e \ne 0$，说明这个元素有被分到权值，也就说明它所在的集合有被选到，最多被选了$f$个，所以$\beta = f$。

所以这个算法是$f$近似的。构造一个例子说明 $f$ 是紧的：

$E= \{ e_{1}, ... e_{n+1} \} , U= \{ \ \{ e_{1}, e_{n} \} , \dots \{ e_{n-1} , e_{n} \} , \{ e_{1}, \dots e_{n+1} \} \ \} , c(s_{1} ... s_{n-1} )=1, c(s_{n} )=1+\epsilon$

那么我们得到的解会是$n+ \epsilon$而最优解是$1+ \epsilon$，因此近似比是$f=n$。

无容量限制选址问题

无容量限制选址问题：有若干待选址地方$F$，有若干顾客$D$，要选择一部分地方建立设施提供服务，使得所有建立的花费加上顾客到设施服务的距离费用之和最小。

这个问题的距离费用满足三角不等式（欧氏距离）。

用$c_{ij}$表示第$j$个顾客到第$i$个设施（若开设）的距离费用。

$y_i = 1$ 表示设施 $i$ 开设，否则等于0；$x_{ij} = 1$ 表示顾客 $j$ 会去 $i$ 接受服务，否则等于0。

整数规划模型：$\begin{aligned} \min & \sum_{i\in F}f_{i}y_{i} + \sum_{i \in F, j\in D}c_{ij}x_{ij} \\ \text{s.t. } & \sum_{i \in F}x_{ij} = 1 \\ & y_{i}-x_{ij} \geq 0 \\ & x_{ij},y_{i} \in \{0,1\} \end{aligned}$

对偶：$\begin{aligned} \max & \sum_{j \in D}v_{j} \\ \text{s.t. } & v_{j}-w_{ij} \leq c_{ij} \\ & \sum_{j \in D}w_{ij} \leq f_{i} \\ & w_{ij} \geq 0 \end{aligned}$

3近似算法：考虑对偶形式，可以在某种程度上认为$v_{j}$是每个顾客的出资，$w_{ij}$表示第$j$个顾客去设施$i$接受服务（可能不是完整服务）的花费。首先对偶问题初始解是$v=0,w=0$，然后逐步提升所有$v_{j}$，当遇到约束时将对应的所有$w_{ij}$一同加入提升集合中并记为紧边，继续提升，直到某些设施满足$\sum_{j \in D}w_{ij} = f_{i}$，记为暂时开放，满足$v_{j}-w_{ij} \leq c_{ij}$的顾客“连上”。

现在有的顾客对很多暂时开放的设施支付了$w_{ij}$，我们希望调整，每个顾客只对他最后相连的设施做贡献，也就是满足原整数规划的等号约束（现在相当于这部分$x_{ij}$是分数）。最后我们可以在对偶解的基础上构造出3近似的可行解。下面是3近似可行解的证明以及第二阶段的构造方法：

• 首先可以得到一张二分图，一侧点是设施，一侧是顾客，对于所有$w_{ij} > 0$的连边，接下来我们只要考虑如何给每个顾客指定一个设施就可以在分数解的基础上构造出整数解了。设这张图为$T$，做$T^{2}$（$(u,v)\in T^{2}$当$dist_{T}(u,v) \leq 2$即相邻或者有一个共同邻居），从$T^{2}$的设施部分导出子图，取最大独立集为$H$。
  • $T^2$解释：如果两个设施有共同的顾客，就给他连边。然后从设施部分导出子图，再取最大独立集$H$。这就是暂时开放的设施集合的子集，它们没有共同的顾客邻点，所以是独立的。又因为是极大独立集，不在$H$的暂时开放设施一定与$H$的某个设施有共同邻点。
  • $H$中的设施正式开放，对应的$y_i=1$。
• 对于顾客$j$，定义满足$v_{j}=w_{ij}+c_{ij}$的顾客为直连，他们支付了建设费用并去接受了完整的服务，其他的顾客为旁连。
• 设$F_{j}$为$H$中跟$j$有连边的设施的集合（$w_{ij} > 0$），由独立集性质可知$F_{j}$至多含有$1$个点。
  • 直连：如果$F_{j}=\{i\}$，直接让$j$去$i$接受服务。
  • 直连：如果$F_{j}=\{\empty\}$，考虑$j$的紧边$(i',j)$，（$w_{ij} = 0$）去找设施$i'$，如果$i'$在$H$中，那么让$j$去设施$i'$接受服务。
  • 如果$j$所有紧边关联设施都不属于$H$。设$i'$为$j$第一个连接上的设施，$i$为任意一个在$H$中与$i'$相邻的设施，让$j$去设施$i$。这部分是旁连。
• 对于顾客$j$，$v_{j}=v_{j}^{f}+v_{j}^{c}$分别是支付给设施建设和自身过去的距离费用。对于直连的，$c_{ij} = v_j^c, \ w_{ij} = v_j^f$。对于旁连的，$v_j^c = v_j, \ v_j^f = 0$。旁连的没有出建设费用。
• 引理：$H$中的设施，与其相连（直连）的顾客出的建设费用和等于$f_i$。
• 引理：对旁连顾客$j$，$c_{ij} \leq 3*v_{j}^{c}$。
  • 考虑四个点的二分图，边集为$(i',j),(i',j'),(i',j')$，其中旁连顾客$j$，给$j$分配到了属于$H$的$i$。由我们的算法过程知道，$j$和$i'$相连，$j'$和$i', i$相连，设施$i$和$i'$相邻。
  • 由于有边连接可知$v_{j}^{c} \geq c_{i'j}, v_{j'}^{c} \geq c_{ij'},v_{j'}^{c} \geq c_{i'j'}$否则在提升时就会被约束卡住，另外我们选择的$i'$是$j$的第一个可能连接上的设施，因此当$v_{j}$不能再提升的时候，一定满足$i$已经筹齐了设施的建设费并且$w_{i'j'} > 0$，因此还有$v_{j}^{c} = v_{j} \geq v_{j'} \geq v_{j'}^{c}$，再由欧氏距离的三角不等式$c_{ij} \leq c_{ij'}+c_{i'j'}+c_{i'j}$，可证$c_{ij} \leq 3 * v_{j}^{c}$
• 定理：以上算法近似比为3。这个很好证明，因为旁连$c_{ij} \leq 3*v_{j}^{c}$，有$\alpha = 1, \beta = 3$。