有关Binpacking问题的定义和其他近似算法见我之前的文章, 本篇主要补充Binpacking问题First Fit算法可以做到1.7的渐进近似比。
First Fit算法: 依次考虑每个物品, 逐个检查当前已经开着的箱子, 发现第一个能装下它的箱子就装。如果都装不下，开一个新的箱子装它。
证明框架
设第$i$个物品的体积是$s_i$.
设计一个权函数$w(x)$, $w(S):= \sum_{i \in S}{w(s_i)}$.
我们用$w(I)$作为桥梁，证明$ALG(I) - \epsilon \leq w(I) \leq 1.7 OPT(I)$, 从而证明1.7的渐进近似比。
权函数$w(x)$的定义如下(数学家们凑出来的):
注意, $bonus(x)$是单调不减的。
第一个不等号的意思是, 算法解除掉少数几个箱子, 剩余的箱子的平均权重至少是1.
第二个不等号实际上是由更强的结论 任意一个箱子$B_j$, $w(B_j) \leq 1.7$ 得到的。
Part1: $w(B_j) \leq 1.7$
只要证明$bonus(B_j) \leq 0.5$.
将物品按照bonus函数的4段分成4类。
- 如果箱子里含有第4类($\gt \frac{1}{2}$)的物品, 那么已经有0.4的bonus, 只要证明剩下的不会超过0.1.
- 如果含有第3类, 那么再也装不下第1类和第2类。 这时候bonus刚好是0.5.
- 如果不含第3类, 最多装2个第2类。显然只装1个第2类最多凑到0.1. 如果装2个第2类, 设体积分别是$x, y$. $\frac{3}{5}(x-\frac{1}{6}) + \frac{3}{5}(y-\frac{1}{6}) = 0.6(x+y)-0.2 \lt 0.1$.
- 如果箱子里面不含有第4类。第2,3类每个物品的bonus最多是0.1, 最多装5个, 因此总的bonus不会超过0.5.
Part2: 算法解除掉最后2个箱子, 剩下的箱子平均权重至少是1.
首先我们拿掉算法解中本来权重就至少是1的箱子, 剩下箱子$B_1 \cdots B_m$, 那么剩下的箱子满足:
- 不含第4类物品。 因为第四类物品的权重至少是1.
- 不会同时含2个第3类物品。 因为任意2个第3类物品的权重之和至少是1.
- $s(B_i) \lt \frac{5}{6}$, 否则权重不算bonus部分就至少是1了。
- 除了最后1个箱子, 剩下的箱子里面至少装了2个物品。 因为First Fit优先放前面的箱子，而物品体积都不超过0.5, 一个箱子至少可以放2个物品。
- 除了最后2个箱子, 剩下的箱子装的物品总体积$\gt \frac{2}{3}$. 假设有一个箱子$\geq \frac{2}{3}$, 那么在它后面的箱子里面装的物品体积都$\in(\frac{1}{3}, \frac{1}{2})$, 也就是都是第3类物品。 根据(4)它后面的箱子除了最后一个箱子每个箱子至少装了2个物品，且都是第3类物品，那么就违反了(2).
Lemma: $\forall 1 \leq i \leq m-2, s(B_i) + bonus(B_{i+1}) \geq 1$.
证明:
设$B_{i+1}$中体积最小的物品体积是$x$, 根据first fit有$s(B_i) + x \gt 1$.
- 因为$s(B_i) \lt \frac{5}{6}$, $x \gt \frac{1}{6}$。
- 因为$B_{i+1}$中不能有2个$\geq \frac{1}{3}$的物品, 且$B_{i+1}$装了至少2个物品, $x \lt \frac{1}{3}$.
- 综合上面2条有
利用上面的引理
因此有$\sum_{i=1}^m{w(B_i)}+0.8 \geq m$.
结合两个part, 得到$ALG-0.8 \leq w(I) \leq 1.7OPT$, 也就证明了 $ALG \leq 1.7OPT+0.8$.