Approximation 近似解

一、Approximation Ratio 近似比

\(\rho(n)\)近似算法 \(\rho(n)-approximation\ algorithm\)

设近似解的答案为\(C\)，最优解的答案为\(C^*\)，则近似算法的近似比\(\rho(n)=max(\frac{C}{C^*},\frac{C*}{C})\)
对于任意输入\(I\)，近似解为求一个上确界
- 求极小值：\(\alpha=sup(\frac{C(I)}{OPT(I)})\)
- 求极大值：\(\alpha=sup(\frac{OPT(I)}{C(I)})\)
- 一般情况下，\(C(I)\)是可以直接计算出来的，而\(OPT(I)\)需要通过放缩得到一个不等式

\(1+\epsilon\)近似算法 \((1+\epsilon)-approximation\ algorithm\)

近似算法的近似比为\(1+\epsilon\)
时间复杂度：多项式时间

多项式近似方案 \(polynomial-time\ approximation\ scheme(PTAS)\)

给定一个常数\(\epsilon\)，算法的近似比为\(1+\epsilon\)
时间复杂度：多项式时间，为\(O(n^k)\)，k与\(\epsilon\)有关
例：\(O(n^{2/\epsilon})\)

完全多项式近似方案 \(fully\ polynomial-time\ approximation\ scheme(FPTAS)\)

给定一个常数\(\epsilon\)，算法的近似比为\(1+\epsilon\)
时间复杂度：多项式时间，为\(O(k*n^\alpha)\)，k与\(\epsilon\)有关，\(\alpha\)为常数
例：\(O((\frac{1}{\epsilon})^2 n^3)\)

二、Approximate Bin Packing 近似装箱问题

2.1 问题描述

给定n个size为\(S_1,S_2,...S_n(0< S_i \le 1)\)的物品，物品不可分割，将这n个物品用最少的箱子装出来，求最少需要多少个箱子
是NPC问题

2.2 算法

2.2.1 NextFit：来一个物品，装入当前箱子，装不下去就新开一个箱子

算法：

void NextFit ( ){   
    read item1;
    while (read item2){
        if (item2 can be packed in the same bin as item1 )
			place item2 in the bin;
        else
			create a new bin for item2;
        item1 = item2;
    }
}

定理：如果M是最优解，则这个算法的解不超过2M-1
证明：即证，如果NextFit算法使用了2M个箱子，则最优解一定至少使用M+1个箱子
- 在极端情况下，最优解算法求出的每个箱子都是满的，即最优解\(\ge\)所有箱子都是满的情况
- 设\(S(B_i)\)为NextFit算法求出的第i个箱子的大小，则
- \(S(B_1)+S(B_2)>1,\ ...\ ,S(B_{2M-1})+S(B_{2M})>1\)
- \(\therefore \sum_{i=1}^{2M} S(B_i)>M\)
- \(\therefore\) 最优解最少需要\(M+1\)个箱子
近似比为2的例子：
- 物品的大小为\(\frac{1}{2}\)、\(\epsilon\)
- 输入：\(\frac{1}{2}\)、\(\epsilon\)交替输入，共2n组(\(n \rightarrow \inf\))
- 最优解：将\(\frac{1}{2}\)成对放入箱子中，然后将所有\(\epsilon\)放入另一个箱子，共需要n+1个箱子
- NextFit的解：将每一组分别放入一个箱子，共需要2n个箱子
- 近似比：\(\alpha = \frac{2n}{n+1} \rightarrow 2\)

2.2.2 FirstFit：来一个物品，从第一个箱子开始找，找到首个能够装进去的箱子

算法：

void FirstFit ( ){   
    while(read item){
        scan for the first bin that is large enough for item;
        //维护一个区间最大值(剩余容量),但是平衡树的key是箱子的编号
        if (found)
			place item in that bin;
        else
			create a new bin for item;
    }
}

定理：如果M是最优解，则FirstFit算法的解不超过\(\frac{17M}{10}\)，且存在一种输入，使得近似解为\(\frac{17(M-1)}{10}\)
1.7的例子：\(\frac{1}{6}-\epsilon\)、\(\frac{1}{3}-\epsilon\)、\(\frac{1}{2}+\epsilon\)
- 物品大小为：\(\frac{1}{6}-\epsilon\)、\(\frac{1}{3}-\epsilon\)、\(\frac{1}{2}+\epsilon\)
- 输入：n个\(\frac{1}{6}-\epsilon\)、n个\(\frac{1}{3}-\epsilon\)、n个\(\frac{1}{2}+\epsilon\)
- 最优解：以\(\frac{1}{6}-\epsilon\)、\(\frac{1}{3}-\epsilon\)、\(\frac{1}{2}+\epsilon\)为一组，共需要\(n\)个箱子
- FirstFit的解：\(\frac{n}{6}+\frac{n}{3}+n\)
- 近似比：\(\alpha = \frac{\frac{n}{6}+\frac{n}{3}+n}{n} = \frac{1}{6}+\frac{1}{3}+1=1.5\)

2.2.3 BestFit：来一个物品，找到空余内存最少的箱子，将物品装进去

2.2.4 On-line Algorithm：在线算法

在装完上一个物品后，就不能再改变了，且装上一个物品时不知道之后的物品的大小
定理：任何一个在线算法的近似比，一定\(\ge\frac{5}{3}\)
证明：对手法，对每一种近似算法，找到一组输入，让近似比\(\ge\frac{5}{3}\)
- 假设有34个体积为1的物体，箱子的容量为50
- 如果算法无法将这些物体放到一个箱子里，则近似比\(\ge\frac{5}{3}\)（最优解为1，而该算法的解至少为2）
- 如果可以，则添加2个物体(17,17)
  - 如果将这两个17装进2个箱子，则再添加2个物体(34,34)，此时近似比\(\ge\frac{5}{3}\)（最优解为3，而该算法的解至少为5）
  - 如果将这两个17装进1个箱子，则再添加3个物体(26,26,26)，此时近似比\(\ge\frac{5}{3}\)（最优解为3，而该算法的解至少为5）

2.2.6 离线算法

定理：离线算法的近似比，一定\(\ge 1.5\)

三、背包问题

3.1 问题描述

有\(n\)个物体，每个物体有两个属性：体积\(w_i\)，价值\(p_i\)，选择一部分物体，要求体积和不超过\(M\)，且最后的价值和最大

3.2 算法

3.2.1 算法1：优先选择单位价值最大的物体

求解近似比：找一个特例，则近似比不会比这个小

假设背包体积为w，有两个物体，一个物体为(\(w=1,p=2\))，另一个物体为(\(w=w,p=w\))
最优解：选择(w,w)的物体，总价值为w
该算法：选择(1,2)的物体，总价值为2
近似比为\(\frac{2}{w}\)

3.2.2 算法2：优先选择价值最大的物体

3.2.3 算法3：选择上述两种算法中，更优的一个解

设\(\frac{p_1}{w_1} \ge \frac{p_2}{w_2} \ge ... \ge \frac{p_n}{w_n}\)，根据算法1，装到第\(k\)个时就装不下去了，则

\(Greedy_1=p_1+p_2+...+p_{k-1}\)，算法1会选择1~(k-1)
\(Greedy_2 \ge p_k\)，算法2会从n开始选，直到装不下，至少选择的价值会大于\(p_k\)

可以证明：\(OPT \le p_1+p_2+...+p_{k-1}+p_k=Greedy_1+Greedy_2\)

因此，该算法的近似比为\(\epsilon = \frac{OPT}{max(Greedy_1,Greedy_2)} \le \frac{Greedy_1+Greedy_2}{max(Greedy_1,Greedy_2)} \le 2\)

四、load balancing

4.1 问题描述

有m个人，n个工作，每个工作有一个时间\(p_i\)，要求每个人的最大工作时间尽可能小

4.2 算法

求近似比，要先对\(OPT\)进行估计，估计出上界/下界

\(OPT \ge p_n\)，每个人的最大工作时间至少为最长的那个工作
\(OPT \ge \frac{mx+p_n}{m}=x+\frac{p_n}{m}\)

\(AIG=x+\frac{p_n}{m}+(1-\frac{1}{m})p_m \le OPT+(1-\frac{1}{m})OPT=(2-\frac{1}{m})OPT\)

\(\epsilon \le 2-\frac{1}{m}\)

错题

1 最大生成树

S：每个点的临边中，边权最大的边的集合

T：图的最大生成树

证明C：最大生成树中的每一条边，至少是某一个顶点的最大临边

2 旅行商问题 TSP

TSP问题：找一条路径，经过所有节点至少一遍，最后回到起点，并且使边权和最小

算法：找到图的最小生成树，从起点开始，按照先根/后根/中序遍历，走完整个生成树

近似比：设该算法的答案为\(C\)，最优解为\(C^*\)，则\(C<C^*<2C\)

最优解一定比\(C\)大：因为最小生成树是TSP问题的一个松弛解(要求更低的解)