# Approximation

## Approximation Ratio

An algorithm has an approximation ratio of $$\rho(n)$$ if, for any input of size $$n$$, the cost $$C$$ of the solution produced by the algorithm is within a factor of $$\rho(n)$$ of the cost $$C^{*}$$ of an optimal solution: $$max(\frac{C}{C^{*}}, \frac{C^*}{C})\le \rho(n)$$

If an algorithm achieves an approximation ratio of $$\rho(n)$$, we call it a $$\rho(n)-approximation\ algorithm$$.

## polynomial-time approximation scheme(PTAS)

An approximation scheme is a polynomial-time approximation scheme if for any fixed $$\epsilon > 0$$, $$ratio\le 1+\epsilon$$, the scheme runs in time polynomial in the size of its input instance. e.g. $$O(n^{2/\epsilon})$$

## fully polynomial-time approximation scheme(FPTAS)

As a special case of PTAS, the run-time of an FPTAS is polynomial in the problem size and in $$1/\epsilon$$ e.g.$$O((1/\epsilon)^2n^3)$$

FPTAS与PTAS的关系可由下图表示：

## Bin Packing Problem

### On-line Algorithm

On-line Algorithm永远不可能最优，可证明$$ratio\ge 5/3$$

• Next Fit
• 算法: 放在当前的bin中，不够则开新的bin
• $$ratio = 2$$
• First Fit
• 算法: 寻找第一个可放的bin，不然开新的bin
• $$ratio = 1.7$$
• Best Fit
• 算法: 寻找放入之后能占得尽可能满的bin，不然开新的bin
• $$ratio=1.7$$

### Off-line Algorithm

• First Fit/Best Fit Decreasing
• 算法: 按照从大到小的顺序排序，然后采用First Fit/Best Fit

## The Knapsack Problem

### fractional version

• 问题表述：背包容量为$$M$$，有N个物体，第i个物体的重量是$$w_i$$，价值为$$p_i$$。允许把物体的$$x_i$$比例装入，利益为$$x_ip_i$$。求利益最大装法。
• optimal algorithm: 选取$$\frac{p_i}{w_i}$$最大的尽可能装，以此类推。

### 0/1 version

• 问题表述：背包容量为$$M$$，有N个物体，第i个物体的重量是$$w_i$$，价值为$$p_i$$。只能选择装入或不装入，装入利益为$$w_ip_i$$。求利益最大装法。
• NP-hard Problem
• greedy算法的$$ratio=2$$

## K-Center Problem

### Approximation

• 一个结论：选取n个点中的若干点，而非选取平面上的任意点。由下图可知，后者的任意方案，都可以通过前者用两倍的半径替代，故$$ratio = 2$$

• 具体算法：通过对目标半径$$r$$进行枚举，判断是否存在$$k$$个圆心的方案，二分查找获得。
• 除非$$P=NP$$，否则K-center问题不存在近似率小于2的逼近算法