清华大学出版社 TSINGHUA UNIVERSITY PRESS 91近似算法的性能 若一个最优化问题的最优值为c*,求解该问题的一个近 似算法求得的近似最优解相应的目标函数值为C,则将该 近似算法的性能比定义为η=mx{在通常情况下,该 性能比是问题输入规模η的一个函数ρ(nη),即 maX ≤pn) 该近似算法的相对误差定义为入=26若对问题 的输入规模n,有一函数)使得n),则称(n)为 该近似算法的相对误差界。近似算法的性能比p(n)与相 对误差界ε(n)之间显然有如下关系:ε(m)≤p(n)-1。3 9.1 近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近 似算法求得的近似最优解相应的目标函数值为c，则将该 近似算法的性能比定义为= 。在通常情况下，该 性能比是问题输入规模n的一个函数ρ(n)，即 ≤ρ(n)。       c c c c * , * max       c c c c * , * max 该近似算法的相对误差定义为= 。若对问题 的输入规模n，有一函数ε(n)使得 ≤ε(n)，则称ε(n)为 该近似算法的相对误差界。近似算法的性能比ρ(n)与相 对误差界ε(n)之间显然有如下关系：ε(n)≤ρ(n)-1。 * * c c − c * * c c − c