近似算法 | XY's blog

概念

提供不比最优解差太多的可行解
定义: 对于最优化问题 $U = \{\Sigma_I, \Sigma_O, L, L_I, M, cost, goal\}$ , A是U的一个一致性算法. 对于所有问题实例$x\in L_I$, A对于x的相对误差$\epsilon_A(x)$定义为 $\epsilon_A(x) = \frac{|cost(A(x)) - Opt_U(x)|}{Opt_U(x)}$ 其中, $Opt_U(x)$是x的最优cost.
对于任意$n\in \mathbb{N}$, 我们定义A的相对误差为 $\epsilon_A(n) = \max\{\epsilon_A(x)| x \in L_I \cap (\Sigma_I)^n\}$
A关于x的近似率$R_A(x)$定义为 $R_A(x) = \max\{\frac{cost(A(x))}{Opt_U(x)}, \frac{Opt_U(x)}{cost(A(x))}\}$
对于任意$n\in \mathbb{N}$, 我们定义A的相对近似率为 $R_A(x) = \max\{R_A(x)| x \in L_I\cap(\Sigma_I)^n\}$
对于任意正实数$\delta>1$, 如果对任意$x\in L_I$, $R_A(x)\le \delta$, 定义A为U的$\delta-$近似算法.
对于任意函数$f:\mathbb{N}\to \mathbb{R^+}$, 如果对任意$n \in \mathbb{N}$, $R_A(x)\le f(n)$, 定义A为U的$f(n)-$近似算法.
对于最小化问题, 有 $R_A(x) = \frac{cost(A(x))}{Opt_U(x)}=1 + \epsilon_A(x)$
对于最大化问题, 有 $R_A(x) = \frac{Opt_U(x)}{cost(A(x))}$
Greedy Makespan Schedule:
- 对于处理时间$p_i$排序, 从最大的开始, 依次将每个任务分配给最先空闲的机器.
- 证明这个算法是MS的2-近似算法:
  - $I = (p_1, p_2, \cdots, p_n, m)$, $p_1>p_2>\cdots>p_n$, 显然有 $Opt_{MS}(I) \ge p_1\ge p_2 \ge \cdots \ge p_n$ 还有 $Opt_{MS}(I) \ge \frac{\sum_{i=1}^np_i}{m}$
  - 对于任意$k = 1, 2, \cdots, n$, 因为$p_k$是$p_1$到$p_k$中最小的, 所以有 $p_k \le \frac{\sum_{i=1}^k p_i}{k}$
  - 分类讨论:
    - 当$n\le m$时, 显然
    - 当$n>m$时, 设$T_l$满足$cost(T_l)=\sum_{r\in T_l}p_r = cost(GMS(I))$, 而k是$T_l$中最大的下标
      - 如果$k\le m$, $|T_l|=1$, 所以$Opt_{MS}(I) = p_1 = p_k$, $GMS(I)$是最优解.
      - 如果$k>m$, 因为其他机器的cost肯定不小于$cost(GMS(I)) - p_k$, 不然$p_k$就不会安排在这个机器, 所以 $\sum_{i=1}^{k-1}p_i\ge m\cdot [cost(GMS(I)) - p_k]$ 再根据上面的式子2, 有 $Opt_{MS}(I)\ge cost(GMS(I))-p_k$ 因此 $cost(GMS(I)) - Opt_{MS}(I)\le p_k\le \frac{\sum_{i=1}^k p_i}{k}$ 最终有 $\frac{cost(GMS(I)) - Opt_{MS}(I)}{Opt_{MS}(I)}\le \frac{(\sum_{i=1}^k p_i)/k}{(\sum_{i=1}^n p_i)/m}\le \frac{m}{k} < 1$ 因此GMS是MS的2-近似算法.
定义: 对于最优化问题 $U = \{\Sigma_I, \Sigma_O, L, L_I, M, cost, goal\}$ , 如果对于所有的输入对$(x, \epsilon)\in L_I\times \mathbb{R^+}$, A可以计算出一个相对误差不大于$\epsilon$的可行解A(x), 而且$Time_A(x, \epsilon^{-1})$有$|x|$的多项式函数上界, 那么A被称为U的多项式时间近似方案(PTAS).而如果$Time_A(x, \epsilon^{-1})$有$|x|$和$\epsilon^{-1}$的多项式函数上界, 那么A被称为U的完全多项式时间近似方案(FPTAS).
PTAS: 任意输入, 想要多小误差都可以在|x|线性时间求解.
FPTAS: 任意输入, 想要多小误差都可以在|x|和$\epsilon^{-1}$线性时间求解(误差越小越慢)

最优化问题分类

NPO问题可以分为下列5类:
- NPO(I): 存在FPTAS的NPO最优化问题
  - 例如背包问题
- NPO(II): 存在PTAS的NPO最优化问题
  - 例如Makespan Schedule
- NPO(III): $U\in NPO$满足
  - 存在$\delta > 1$, 有多项式时间$\delta-$近似算法
  - 没有PTAS. (即存在$d<\delta$, U无$d-$近似算法)
  - 例如最小顶点覆盖, $\Delta-$TSP, MAX-SAT
- NPO(IV): $U\in NPO$满足
  - 存在多项式时间$f(n)$近似算法, 且f有多项式上界
  - 在某些假设下, 不存在任何$\delta-$近似算法
- NPO(V): $U\in NPO$满足对于所有可能存在的$f(n)-$近似算法, $f(n)$都没有多项式上界
  - 例如TSP, 最大团
在$P\ne NP$的前提下, 每一类都非空

近似算法的稳定性

一般认为NPO(V)中的问题是不可求解的, 但是可以将$U\in NPO(V)$的输入$L_I$根据难度划分.
对于最优化问题 $U = \{\Sigma_I, \Sigma_O, L, L_I, M, cost, goal\}$ 和 $\overline U = \{\Sigma_I, \Sigma_O, L, L, M, cost, goal\}$ , $L_I\subseteq L$, $\overline U$关于$L_I$的距离函数$h_L:L\to \mathbb{R^{\ge 0}}$满足如下性质:
- 对于所有$x\in L_I$, 有$h_L(x)=0$
- h是多项式时间可计算的
对于$\overline U$关于$L_I$的距离函数$h$, 对于任意$r\in \mathbb{R}$, 定义 $Ball_{r,h}(L_I) = \\{w\in L| h(w)\le r\\}$
A是$\overline U$的一致性算法, 也是$U$的$\epsilon-$近似算法($\epsilon \in \mathbb{R^{>1}}$). 令p为正实数.
当对于所有实数 $0 < r\le p$, 存在$\delta_{r, \epsilon}\in \mathbb{R^{>1}}$满足A是$U_r= \{\Sigma_I, \Sigma_O, L, Ball_{r,h}(L_I), M, cost, goal\}$的$\delta_{r, \epsilon}-$近似算法, 我们定义A关于h是p-稳定的
如果对于所有正实数p, A都是p-稳定的, 那么A关于h是稳定的; 如果对于任意正实数p, A都不是p-稳定的, 那么A关于h是不稳定的
TSP和$\Delta-$TSP:
- 对于任意输入实例(G, c), 定义 $dist(G,c)=\max\{0, \max\{\frac{c(\{u, v\})}{c(\{u, v\})+c(\{p,v\})}-1|u, v, p\in V(G), u\ne v, u\ne p, v\ne p \}\}$ $dist_k(G,c)=\max\{0, \max\{\frac{c(\{u, v\})}{\sum_{i=1}^m c(\{p_i,p_{i+1}\})}-1|u, v\in V(G), u=p_1, p_2, \cdots, p_m=v$ $\text{ is a simple path between u and v of length at most }k(m + 1\le k) \}\}$ 对于任意整数$k>2$, $distance(G,c) = \max\\{disk_k(G,c)|2\le k\le|V(G)|-1 \\}$ $Ball_{r, dist}(L_\Delta)$包含满足下面条件的带权图 $c(\{(u,v)\})\le (1+r)(c(\{(u,p)\}) + c(\{(p,v)\}))$
只有在h合理划分问题实例的时候才是有意义的
U和$\overline U$, h, $U_r$定义同上, 令$A=\{A_\epsilon\}_{\epsilon>0}$是U的一个PTAS
- 如果对所有的$r>0$和$\epsilon>0$, $A_\epsilon$是一个$U_r $的$\delta_{r,\epsilon}-$近似算法, 那么A关于h是稳定的
- 如果$\delta_{r,\epsilon}\le f(\epsilon)\cdot g(r)$, 其中
  - f和g是从$\mathbb R^{\ge 0}$到$\mathbb {R^+}$的函数,
  - $\lim_{\epsilon\to 0}f(\epsilon) = 0$
    那么A关于h是超稳定的

对偶近似算法

当限制条件不明确时, 可以找一个不比$Opt_U(I)$差的解, 允许$S\not\in M(I)$, 但是S离M(I)”不太远”
对于最优化问题U, 定义限制条件距离函数为满足如下性质的函数$h: L_I \times \Sigma^*_O\to \mathbb R^{\ge 0}$
- 对于$S\in M(x)$, $h(x, S)=0$
- 对于$S\not\in M(x)$, $h(x, S)>0$
- h是多项式时间可计算的
例如01背包问题中, 定义 $h(I, T)=\max\{0, \max\{\sum_{l\in T_i}p_l|i=1,2,...,m \}-1\}$ 如果存在$\epsilon$满足对任何$i=1,2,…,m$有$\sum_{l\in T_i}p_l\le 1 + \epsilon$, 则$T\in M_\epsilon^h(I)$
定义满足如下条件的算法A为U的$h-$对偶$\epsilon-$近似算法: 对所有$x\in L_I$, 有
- $A(x)\in M_\epsilon^h(x)$
- 如果目标是最大化, 则$cost(A(x))\ge Opt_U(x)$, 如果目标是最小化, 则$cost(A(x))\le Opt_U(x)$

定义满足如下条件的算法A为U的$h-$对偶多项式时间近似方案(h-dual PTAS for U):
- 对于任意输入$(x,\epsilon)\in L_I\times \mathbb R^+$, $A(x, \epsilon)\in M_\epsilon^h(x)$
- 如果目标是最大化, 则$cost(A(x,\epsilon))\ge Opt_U(x)$, 如果目标是最小化, 则$cost(A(x,\epsilon))\le Opt_U(x)$
- $Time_A(x, \epsilon^{-1})$有$|x|$的多项式函数上界

如果$Time_A(x, \epsilon^{-1})$有$|x|$和$\epsilon$的多项式函数上界, 则A为U的$h-$对偶完全多项式时间近似方案(h-dual FPTAS for U)