Approximation Ratio Optimization problem: 。instance: OPT(1)=optimum of instance I algorithm:SOLA()=output of on instance I Minimization:algorithm has approximation ratio a >1 SOL( if V instance 1: ≤a OPTD Maximization:algorithm has approximation ratio a 1 SOL() if V instance 1:- OPT1 。e-approximation: (1-e)OpT()<soL(n<.(1te)OPT() (maximization) (minimization)• Optimization problem: • instance : = optimum of instance • algorithm : = output of on instance • Minimization: algorithm has approximation ratio if instance : • Maximization: algorithm has approximation ratio if instance : • -approximation: I OPT(I) I 풜 SOLA(I) 풜 I 풜 α ≥ 1 ∀ I SOL풜(I) OPT(I) ≤ α 풜 α ≤ 1 ∀ I SOL풜(I) OPT(I) ≥ α ϵ (1 − ϵ)OPT(I) ≤ SOL풜(I) ≤ (1 + ϵ)OPT(I) Approximation Ratio (maximization) (minimization)