Question

#3. 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). • OPT 25 • OPT<5 • OPT> 80 • OP T S 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.

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 upvote if you like the answer and comment for any query.