装箱问题近似算法分析

近似算法性能比

对于优化问题 $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$ 个物品，物品大小为 $ 0a_1,a_2,…,a_n $ , 箱子尺寸 $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$，绝对性能比为 $-$, 即 $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】的函数图像为：

分解上述问题

要证明 \[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 \]

如果所有物品体积 $c$ 均有 \[c\le\frac{1}{6}\]：
$v(a) = 0$, 箱子权重就是箱子中物品体积总和的1.2 倍，$w(B)\le 1.2$
如果存在物品体积 $c$ 有 $\frac{1}{6}<c\le \frac{1}{3}$:
这种物品在一个箱子内至多有5 个，且每个物品 $v(a)\le0.1$ ，因此 bonus 不会超过 0.5, 权重$w(B)\le 1.7$
如果存在两个物品体积 $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$
如果存在三个物品体积 $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$
其他情况同理分析

因此，$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。可以剔除掉的箱子有：

装有一个 large item (体积大于等于 1/2的物品)：$w(B)\ge1.2\times 0.5+0.4=1$
箱子内物品总体积大于 5/6：\[w(B) \ge 1.2\times \frac{5}{6} = 1\]
装有两个体积大于等于 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，已经被剔除。

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

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

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

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

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

下证: \[\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：只考虑大于 $$ 的物品, 每个箱⼦最多装 $$ 个

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

\[ \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 不成立：物品类型不是常数种：将其变成常数种：将所有的物品分成常数组，同一组内物品的体积都调整一致，相当于有常数种物品类型。

对物品按照体积从小到大排序，将物品分成 $ $ 组，每组有 $ n ^2$ 个物品

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

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

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

\[ \begin{align} OPT(J)&\le OPT(J')+\theta\\ &\le OPT(I)+\theta\\ \theta &\le n\epsilon^2\\ \end{align} \]

又每个箱子最多装 $$ 个物品，至少用 $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-$ ,

\[ \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)\]