Suppose you have a minimization problem and an algorithm A t

Suppose you have a minimization problem and an algorithm A, that has a performance guarantee 3. When run on some input I, A produced a solution with cost 12. What can you say about the true (optimal) answer OPT? OP T greaterthanorequalto 4 OP T lessthanorequalto 4 OP T greaterthanorequalto 12 OP T lessthanorequalto 12 OP T greaterthanorequalto 36 OP T lessthanorequalto 36

Solution

the performance and the cost are inversly proportional

because the performance must be high as well as the cost must be low inorder to get the profits

as in this case the performance guarentee factor=3

cost of runinng the algorithm is 12

therefore p=1/c

so we can say that from the above equation opt<=p*c

opt<=3*12

opt<=36