PTAS and FPTAS Optimization problem: 。instance: OPT(I)=optimum of instance I algorithm SOL(e,I=output of A on I and 0<e<1 。e-approximation: (1-e)OPTI)≤SOL(e,)≤(1+e)OPT) (maximization) (minimization) Algorithm is a PTAS(Polynomial-Time Approximation Scheme) if for every 0<e<1 and instance I,it returns an e-approximation in poly()time,where I is the length of I in binary code. Algorithm is a FPTAS(Fully Polynomial-Time Approximation Scheme)if for every 0<e<1 and every instance I,it returns an e-approximation in poly(1/e,I)time.• Optimization problem: • instance : = optimum of instance • algorithm : = output of on and • -approximation: I OPT(I) I 풜 SOL풜(ϵ, I) A I 0 < ϵ < 1 ϵ (1−ϵ)OPT(I) ≤ SOL풜(ϵ, I) ≤ (1+ϵ)OPT(I) PTAS and FPTAS (maximization) (minimization) Algorithm is a PTAS (Polynomial-Time Approximation Scheme) if for every and instance , it returns an -approximation in time, where is the length of in binary code. Algorithm is a FPTAS (Fully Polynomial-Time Approximation Scheme) if for every and every instance , it returns an -approximation in time. 풜 0 < ϵ < 1 I ϵ poly(|I|) |I| I 풜 0 < ϵ < 1 I ϵ poly(1/ϵ, |I|)