Question

Suppose you have a minimization problem and an algorithm A, that has an approximation ratio of 4. When run on some input I, A produced a solution with cost 20. What can you say about the optimal answer (let's call it OPT)? Mark “true" or "false" for inequalities below and briefly explain your answer(s). • OP T5 • OP T < 5 • OP T >80 • OP T < 80

Answer 1

Approximation ratio ρ(n) is the ratio of cost or result obtained by the algorithm and the optimal cost. For minimization problem it can be calculated using the equation c/c* <= ρ(n).

Where, c = cost of the solution

c* = optimal cost of the solution.

Here in the given question c= 20, ρ(n)= 4 and we have to find the value of c*.

solving the equation,

20/c* <= 4

this equation holds true for any value of c* >=5(refer to image for explanation) thus, OPT >=5 is the correct answer.

for Minimization Problem, C i Plo) C* C = 20 Pln) = 4 ( cost og Solution given) ( Approximation Ratica) 20 r Plo) c* c* 20 Pln) 20 c* 4 5 c* AR cx is also called optimal Cost OPT 75 ar OPT

OPT>= 5: True, as explained above it satisfies the equation.

OPT< 5: False, equation does not satisfy for any value of c* less than 5.

OPT >80: True, any value greater than 80 will also be greater than 5 thus this condition satisfies the solution.

OPT <= 80: False, 2 is less than 80 but it does not satisfy c*>=5 and in OPT<=80 negative numbers will also come therefore this condition is false.

_{please give POSITIVE rating if you understood the answer thank you..}