Approximation

对于一维装箱问题,除非$P=NP$,否则不可能存在近似比小于$\frac 32$的算法.

在线算法(online):

• $Next \ Fit$:只要装不下了,就新开一个箱子,如果最优解用$M$个箱子,那么nf最多用$2M-1$个箱子;
• $First \ Fit$:按箱子打开的顺序从早到晚检查,将物品放入第一个能放下的箱子中;
• $Best\ Fit$:将物品放入剩余空间最小的箱子中,最大化利用箱子空间;
• $Worst \ Fit$:将物品放入剩余空间最大的箱子中.

---

离线算法(offline):

• FFD:如果最优解用M个箱子,那么FFD最多用$\frac{11M}{9}+\frac 69$个箱子

$Next \ Fit$近似比是2

FF和BF近似比都是1.7

$0-1$背包问题,近似比是2.但是如果已知最优解中价值最大的前$k$个,那么可以设计出近似比为$\frac{k+1}{k}$的算法

$k-center$问题近似比是2.

• PTAS:是$n$的多项式,但不是$\epsilon$的多项式
• FPTAS:是$n$和$\epsilon$的多项式