Dylan's Blog

基础概念

1. 问题 $\pi$，最大化或最小化问题
2. 实例(instance) $I$
3. $I$ 的可行解集合 $S(I)$，需满足
   • 可行解 $s$ 大小为 $|I|$ 的多项式($|s|\in poly(|I|)$)
   • 多项式时间能判断解 $s$ 是否可行($s\in S(I)$)
4. 目标函数(objective function) $obj(I, s)$，需满足
   • $obj(I, s) \geq 0$
   • 给定 $I,s$ 时，目标函数能在多项式时间内算出
5. 最优解 $OPT(I)$, 算法所得解 $ALG(I)$
6. $\alpha$ 近似(factor-$\alpha$-approximation)：最小化问题为例，对于任意一个实例 $I$，算法给出的解 $s$ 都满足 $\frac{obj(I,s)}{OPT(I)} \leq \alpha$