近似算法性能比

对于优化问题 $D$，近似算法 $A$

在实例 $I$ 上的性能比：性能比大于等于 1， 越接近 1 越好

$$
R_A(I)=\max{\frac{OPT(I)}{A(I)},\frac{A(I)}{OPT(I)}}
$$

绝对性能比：性能比上界集合中的下确界(最大下界)

$$
R_A= \inf{ r\vert R_A(I) ≤r, ∀I∈D }
$$

渐近性能比:
$$
R_A^{\infty} = \inf{r\vert\exists N\in Z^+, R_A(I) ≤r,for\ ∀I∈D\ with\ OPT(I)\ge N}
$$

显然有：$$ 1\le R_A^{\infty}\le R_A\le\infty$$, 但不一定有 $$R_A^{\infty}=R_A$$。渐进性能比不考虑一些特殊的实例到来的影响，而更考虑算法在实例较大时的性能。

问题描述

设有 $n$ 个物品，物品大小为 $ 0\le a_1,a_2,…,a_n\le 1 $ , 箱子尺寸 $c = 1$ 。希望用最少的箱子装下所有物品，求使用箱子的个数。

近似算法

  • First-Fit (FF)：选择最先打开的可以装下的箱子
  • Best-Fit：选择能装下的箱子中剩余空间最少的箱子
  • Next-Fit：若当前箱子能装则装入，否则打开新的箱子 （不看前面的箱子）

简单分析

如果 $$a_i>\frac{1}{2}$$ ，记为 large item。每个 large item 占一个箱子。因此， large item 的个数构成了一个下界。

绝对性能比不小于 3/2

由于装箱问题是 NPC问题，则 ‘给定一定的物品实例 $I$，判定能否用两个箱子装下 ‘ 也是NPC问题

若存在多项式时间的近似算法 $A$，绝对性能比为 $\frac{3}{2}-\epsilon $, 即 $A(I)\le(\frac{3}{2}-\epsilon )OPT(I)$。则若

  • $$A(I)<3,$$ $$OPT(I)\le A(I)\le2$$
  • $$A(I)\ge3$$, $$OPT(I) \ge A(I)/(\frac{3}{2}-\epsilon)\ge3/(\frac{3}{2}-\epsilon)>2 $$

这表明用这个近似算法解决上述 NPC问题，矛盾。

因此 【在P≠NP的假设下】，不存在绝对性能比小于 3/2 的多项式时间近似算法。

$$\ FF(I) \le 1.7 OPT (I)+1 $$

记：

  • $FF(I)$: 表示对实例 $I$ 运⽤ first fit 得到的箱子数
  • $OPT(I)$: 表示对实例 $I$ 的最优箱子数
  • $B$ : first fit算法得到的装箱⽅案
  • $B^*$ : 最优解的装箱⽅案
  • $c(B_j)$: 第 $j$ 个Bin中 item 体积总和
  • $ w(B_j)$: 第 $j$ 个Bin中 item 权重总和 (后面说明)

均摊分析 (amortized analysis)

做⼀个映射：对每一个 item，$a_i$ 将其映射到一个权重 $w(a_i)$ 。有：

$$
w(B) = \sum_{a_i\in B}w(a_i)\
w(I) = \sum_{i=1}^nw(a_i)\
w(I) = \sum_{i=1}^nw(a_i)=\sum_{j=1}^{FF(I)}w(B_j) = \sum_{j=1}^{OPT(I)}w(B_j^*)
$$

设计权重函数

$$
\begin{align}
w(a) &= \frac{6}{5}a+v(a)\
v(a) &=\left{
\begin{array}{rcl}
0 & & {a \le \frac{1}{6}}\
\frac{3}{5}(a-\frac{1}{6}) & & {\frac{1}{6}< a \le \frac{1}{3}}\
0.1 & & {\frac{1}{3}< a \le \frac{1}{2}}\
0.4 & & { a > \frac{1}{2}}
\end{array} \right.
\end{align}
$$

$v(a)$ 【对于每个权重的bonus】 的函数图像为：

image-20200129115708498

分解上述问题

要证明 $$FF(I) \le 1.7 OPT (I)+0.8$$ 只需证： $$1.\ w(I) \le 1.7 OPT (I),\ 2.\ FF(I) \le w(I)+0.8$$

1. $\ w(I) \le 1.7\ OPT (I)$

若证明 $$\forall B_j^*,w(B_j^*)\le 1.7$$, 则 $$w(I)= \sum_{j=1}^{OPT(I)}w(B_j^*)\le 1.7OPT(I)$$ 。先证明：对任意可行的箱子，$$w(B)\le 1.7$$ 。

首先有：$$w(B) = 1.2\sum_{a_i\in B}a_i+\sum_{a_i\in B}v(a_i)\le1.2 +bonus $$

  1. 如果所有物品体积 $c$ 均有 $$c\le\frac{1}{6}$$：
    $v(a) = 0$, 箱子权重就是箱子中物品体积总和的1.2 倍，$w(B)\le 1.2$
  2. 如果存在物品体积 $c$ 有 $\frac{1}{6}<c\le \frac{1}{3}$:
    这种物品在一个箱子内至多有5 个，且每个物品 $v(a)\le0.1$ ，因此 bonus 不会超过 0.5, 权重$w(B)\le 1.7$
  3. 如果存在两个物品体积 $c_1$ 和 $c_2$ 有 $$c_1>\frac{1}{2}$$ 且 $$\frac{1}{3}<c_2\le\frac{1}{2}$$
    其它物品的体积都不会超过$\frac{1}{6}$ ，没有bonus；$c_1$ 和 $c_2$ 带来的bonus 恰为0.5, $w(B)\le 1.7$
  4. 如果存在三个物品体积 $c_1$, $c_2$ 和 $c_3$ 有 $$c_1>\frac{1}{2}$$ , $$\frac{1}{6}<c_2,c_3\le\frac{1}{3}$$ 且 $c_2 + c_3 < \frac{1}{2}$
    其它物品的体积都不会超过$\frac{1}{6}$，没有bonus；且 $\frac{3}{5}(c_2-\frac{1}{6})+\frac{3}{5}(c_3-\frac{1}{6} )<0.1$，再加上 $c_1$ 带来的bonus 0.4, $w(B)\le 1.7$
  5. 其他情况同理分析

因此，$w(B)\le 1.7$ ，$w(I)= \sum_{j=1}^{OPT(I)}w(B_j^*)\le 1.7\ OPT(I)$ 。

2. $$\ FF(I) \le w(I)+1$$

不考虑 $w(B)\ge 1$ 的箱子：他们已经满足均值至少为 1。可以剔除掉的箱子有：

  1. 装有一个 large item (体积大于等于 1/2的物品)：$w(B)\ge1.2\times 0.5+0.4=1$
  2. 箱子内物品总体积大于 5/6：$$w(B) \ge 1.2\times \frac{5}{6} = 1$$
  3. 装有两个体积大于等于 1/3 的物品：$$w(B) \ge 1.2\times \frac{2}{3}+0.1+0.1=1$$

考虑剩下的 $w(B)<1$ 的箱⼦ (仍按原来 First Fit 的顺序摆放), 有两个结论：

A.除了最后两个箱子, 其它箱子内物品总体积大于 2/3

证明：如果有一个箱子内物品总体积 $size\le2/3$ 。有 First Fit 算法，后面箱子内的物品体积都大于 1/3 (否则可以放在该箱子中)。又一个箱子内不会有两个体积大于 1/3 的物品 (否则权重大于1，已经剔除)，因此后面箱子内最多只有一个物品，且物品体积小于 1/2 (否则权重大于1，已经剔除)。若后面还有箱子，则里面物品体积需大于等于 1/2，已经被剔除。

image-20200129132126133

因此，最多只有最后两个箱子体积小于等于 2/3。如下图, 其中 $B_{k+2}$ 不一定存在

image-20200129133412717

B.除了最后⼀个箱子, 其它箱子中⾄少有两个物体

除了最后两个箱⼦，其他箱⼦内物品总体积都大于 2/3，且每个物体的体积都小于 1/2，因此每个箱⼦⾄少装两个物品。

对于倒数第⼆个箱子，如果箱⼦内物品总体积小于等于 2/3，箱⼦内物品总体积应⼤于 1/2，否则 最后一个箱子里的物品体积就要大于等于 1/2，这不可能。因此，倒数第二个箱子也⾄少装两个物品 。

令 $x = 1-s(B_j)$，即表示箱子剩余的空间。$x>1/6$。下一个箱子中至少有两个物品$P,Q$

image-20200129135804719

下证: $$\frac{6}{5}s(B_j) + v(B_{j+1}) \ge 1,j=1,2,…,k $$:

$$
\begin{align}
&\frac{6}{5}s(B_j)+ v(B_{j+1})\
\ge& \frac{6}{5}s(B_j)+ v(P)+v(Q)\
\ge& \frac{6}{5}(1-x)+ \frac{3}{5}(x-\frac{1}{6})\times 2\
=&\ 1
\end{align}
$$

也就是说, 对于大于2/3的箱子, ⼀个箱⼦的 size (箱子内物品总体积) 和下个箱⼦的 bonus 之和大于等于 1。即

$$
\sum_{i=1}^kw(B_i) + v(B_{k+1}) = v(B_i)+\sum_{j=1}^k [\frac{6}{5}s(B_j) + v(B_{j+1})] \ge k
$$

对于小于等于 2/3 的箱子:

若有两个小于等于 2/3 的箱子, 一共有 $k+2$ 个箱子。 $s(B_{k+1}) + s(B_{k+2}) \ge 1$ (否则可以装在一个箱子里)

$$
\begin{align}
w(I) &= \sum_{i=1}^kw(B_i) + 1.2[s(B_{k+1}) + s(B_{k+2})] +v(B_{k+1}) + v(B_{k+2}) \
&\ge \sum_{i=1}^kw(B_i) + v(B_{k+1}) + 1.2[s(B_{k+1}) + s(B_{k+2})] \
&\ge k + 1.2\
&= (k+2) -0.8 \
&= FF(I) -0.8
\end{align}
$$

若有一个小于等于 2/3 的箱子, 一共有 $k+1$ 个箱子。由于前面箱子内物品总体积不超过 5/6, 因此最后一个箱子内物品体积大于等于 $1/6$ 。

$$
\begin{align}
w(I) &= \sum_{i=1}^kw(B_i) + 1.2\times s(B_{k+1}) +v(B_{k+1})\
&\ge \sum_{i=1}^kw(B_i) + v(B_{k+1}) + 1.2 \times \frac{1}{6} \
&\ge k + 0.2\
&= (k+1) -0.8 \
&= FF(I) -0.8
\end{align}
$$

若 $k=0$, 亦满足 $$\ FF(I) \le w(I)+1$$。

证毕. $$FF(I) \le 1.7\ OPT (I)+ 1$$

@_@ 现在的最新结果好像是：$$ FF(I) \le 1.7\ OPT (I)$$

$$\ A(I) \le (1+\epsilon ) OPT(I)+1 $$

假设1：只考虑大于 $\epsilon $ 的物品, 每个箱⼦最多装 $\lfloor \frac{1}{\epsilon}\rfloor $ 个

假设2：若物品的类型只有常数 $k$ 种。引入向量 $[b_1,b_2,…,b_k], b_i$ 表示一个箱子中第 i 类的物品装的个数，范围为 $[0,\lfloor \frac{1}{\epsilon}\rfloor ]$ 。一个向量构成了装箱的一个模式，共有 $ k^{\lfloor \frac{1}{\epsilon}\rfloor } $ 种可能。则装箱问题的线性规划为：

$$
\min \sum_{j=1}^M x_j\
\sum_{j=1}^Mt_{ji}x_j\ge b_i,i=1,…,k\
x_j\in \mathbb{Z}^+(x_j\ge 0)
$$

  • $x_j$: 第 j 种装箱模式使用的个数
  • $t_{ji}$: 第 j 种装箱模式中第 i 个物品的个数
  • $b_i$: 第 i 中物品的总数

可以在多项式时间内求解。

假设2 不成立：物品类型不是常数种：将其变成常数种：将所有的物品分成常数组，同一组内物品的体积都调整一致，相当于有常数种物品类型。

对物品按照体积从小到大排序，将物品分成 $ \lfloor \frac{1}{\epsilon^2}\rfloor $ 组，每组有 $ n \epsilon^2$ 个物品

image-20200131214709397

向上 rounding 【记为 J 】：组内物品的体积变为组中物品体积的最大值。可用多项式时间求解。此时用的箱子数大于等于原问题的箱子数 ： $$ OPT(J)\ge OPT(I)$$

image-20200131214905592

向下 rounding 【记为 J’ 】：组内物品的体积变为组中物品体积的最小值。可用多项式时间求解。此时用的箱子数小于等于原问题的箱子数 ： $$ OPT(J’)\ge OPT(I)$$

image-20200131214943370

由于物品从小到大排序，第 i 个分组的体积最大值小于等于第 i+1 个分组的体积最小值。因此，J 中除了最后一个组外用的箱子少于等于 J’ 用的箱子数。而最后一个组最多有 $ n \epsilon^2$ 个物品，因此最多用 $ n \epsilon^2$ 个箱子。

image-20200131220603216

$$
\begin{align}
OPT(J)&\le OPT(J’)+\theta\
&\le OPT(I)+\theta\
\theta &\le n\epsilon^2\
\end{align}
$$

又每个箱子最多装 $\lfloor \frac{1}{\epsilon}\rfloor $ 个物品，至少用 $n\epsilon$ 个箱子:

$$
OPT(I)\ge\frac{n}{1/\epsilon}=n\epsilon\
\theta \le n\epsilon^2\le\epsilon OPT(I)\
OPT(J)\le (1+\epsilon)OPT(I)
$$

假设 1 不成立：考虑体积小于 $\epsilon$ 的物品：

  • 如果这些物品都能被装在这OPT(J)个箱⼦中，则 $OPT(J)\le (1+\epsilon)OPT(I)$ 仍成立

  • 否则，如果打开了新的箱子，那前面的箱子装的物品体积一定大于 $1-\epsilon $ ,

    $$
    \sum_{i=1}^na_i>(1-\epsilon)(OPT(J)-1)\
    OPT(I)\ge\sum_{i=1}^na_i\
    OPT(J)\le \frac{1}{1-\epsilon}OPT(I)+1
    $$

@_@ 现在的最新结果好像是：$$ 2.\ A(I) \le (1+\epsilon ) OPT(I)$$

递减首次适合 (First Fit Decreasing FFD)

将物品根据体积进行递减排序后进行首次适应算法。

$$R_{FFD}^\infty = \frac{11}{9}$$

现在似乎证明了 $$ FFD(I) \le \frac{11}{9}OPT(I)+\frac{6}{9}$$。可以简单证明不小于$$\frac{11}{9}$$，设实例为：

  • $$\frac{1}{2}+\epsilon$$ 的物品有 6m 个
  • $$\frac{1}{4}+2\epsilon$$ 的物品有 6m 个
  • $$\frac{1}{4}+\epsilon$$ 的物品有 6m 个
  • $$\frac{1}{4}-2\epsilon$$ 的物品有 6m 个

则 OPT需要的箱子数为 9m 个，FFD使用的箱子数为 11m个。由于m可以无限大，近似比不小于$$\frac{11}{9}$$

$$R_{FFD} = \frac{3}{2}$$

只需证明 $$FFD(I) \le \frac{3}{2}OPT(I)$$

作业题，不难的^ ^

近似比为1.5的线性时间算法

简单思路：

  1. 将物品分为大物品（体积大于1/2）和小物品，大物品各占一个箱子
  2. 用小物品填满装有大物品箱子，小物品超出箱子的部分切开，装满后可以开新的箱子
  3. 将切开的物品合在一起放到新的箱子里

证明：第2步使用的箱子数 $k$ 一定小于最优解（箱子全部装满了）。第 3 步中使用的箱子一定少于 $k/2$ （被切开的物品最多有 $k$ 个，且都是小物品，每个箱子至少可以装两个物品）。因此最多使用 $3/2k$ 个箱子，近似比不大于1.5。

// 感谢mcl同学的笔记与图片