Approximation Algorithm -

Anonymous included in Algorithm

2023-12-22 2024-05-18

Contents

基本概念

近似算法产生解的代价：C，最优解产生解的代价：$C^*$

$max(\frac{C}{C^*}, \frac{C^*}{C}) \le \rho(n)$ <=> 近似算法有近似比 $\rho(n)$, 近似算法是一个相对近似算法

特别的，如果算法近似比达到$\rho(n)$，则该算法为$\rho(n)$近似算法

$\left| C - C^* \right| \le k$, k是一个常数 <=> 近似算法是一个绝对近似算法

上面取max和绝对值，是因为面对的可能是一个最大化问题，也可能是一个最小化问题

一个最优化问题的一种近似模式实际就是指的一种近似算法，这种近似算法满足如下条件：

输入除了该问题的实例外，还有一个值$\varepsilon > 0$, s.t. 对任何固定的$\varepsilon$, 该模式是一个$(1 + \varepsilon)$近似算法

在众多近似模式中，有两种特殊的，分别是：多项式时间近似模式 和 完全多项式时间近似模式。它们二者在近似模式要求的基础上，对近似算法的时间复杂度做了进一步的要求。

多项式时间近似模式除近似模式本身对于近似比的要求外，还要求近似算法的时间复杂度是n的多项式。

完全多项式时间近似模式除近似模式本身对于近似比的要求外，还要求近似算法的时间复杂度既是$\frac{1}{\varepsilon}$的多项式，又是n的多项式

如果看待多项式时间近似模式和完全多项式时间近似模式的区别？

二者都一定是满足近似算法的基本要求的，除此以外，区别进在于时间复杂度。显然的是，近似比越接近接近于1 / $\varepsilon$越接近于0，说明近似结果同最优解越接近，近似效果越小。

多项式时间近似模式仅要求复杂度是n的多项式，这并不排除$\frac{1}{\varepsilon}$成为n的指数。当$\varepsilon$减少时，指数位置会使得时间复杂度迅速增长，而系数位置则确保了$\varepsilon$的常数倍减小只会使得时间常数倍增大。

贪心策略：按输人的顺序分配作业，把每一项作业分配给当前负载最小的机器。如果当前负载最小的机器有 2 台或 2 台以上,则分配给其中的任意一台。
近似比：2近似算法, $G-MPS(I) \le (2 - \frac{1}{m}) OPT(I)$
证明: 1.最小化问题找最优解的下界 2.考虑算法的最终结果等于最终负载最大的机器，考虑最后一项分配到该机器上的作业，分配之前此台机器是负载最小的机器，从而时间小于等于均值

若假设代价函数满足三角不等式则2近似算法
若代价函数不满足三角不等式，则在$P \ne NP$前提下，不存在$\rho (\rho > 1)$近似算法，$\varepsilon$-近似旅行商问题是NP难问题

1-近似算法：将程序按照所需存储空间由小到大编号，然后逐一向第一个磁盘存储，第一个磁盘不能存储时，再将剩下的程序逐一向第二个磁盘存储，直至第二个磁盘也不能存储为止。