Computer Science Background Knowledge NP-complete Problems: unlikely to have a polynomial time algorithm to optimally solve the problem A-an approximation algorithm for a minimization problem performance ratio: a number r such that for any instance I A1)OPT)≤r A()- the cost of the solution for instance I produced by A OPTO-the cost of an optimal solution for instance I approximation scheme: an algorithm A with input I and an error bound a that has the performance ratio 1+8 a family of algorithms A, one for each a. 2021/1/29 122021/1/29 12 Computer Science Background Knowledge NP-complete Problems: unlikely to have a polynomial time algorithm to optimally solve the problem A- an approximation algorithm for a minimization problem. performance ratio: a number r such that for any instance I A(I)/OPT(I)  r A(I) - the cost of the solution for instance I produced by A OPT(I) - the cost of an optimal solution for instance I. approximation scheme: an algorithm A with input I and an error bound  that has the performance ratio 1+ . a family of algorithms A, one for each 