Question 1: (8 points) Professor Clever has designed an approximation algo- rithm ALG for the scheduling...

Transcribed Image Text:

Question 1: (8 points) Professor Clever has designed an approximation algo- rithm ALG for the scheduling problem P||Cmax, i.e., the problem of minimizing makespan on identical parallel machines. He claims that his algorithm is a 1.5- approximation algorithm. We run ALG on some instance I with m machines and n jobs with processing times p₁,...,Pn. We find out that the cost (length) of the schedule found by the algorithm is more than 2 times the value Σ, p₁/m (which we know is a lower bound on the optimal value.) (a) (2 points) Based on this information, can we conclude that professor Clever's claim must be false? Explain your answer. (b) (3 points) Now, the same question but with the additional information that Pj E {1,2} for each job in our instance I. (c) (3 points) Again, the same question but with the additional information that Pj E {2,3} for each job in our instance I and n ≥ 5m. Question 1: (8 points) Professor Clever has designed an approximation algo- rithm ALG for the scheduling problem P||Cmax, i.e., the problem of minimizing makespan on identical parallel machines. He claims that his algorithm is a 1.5- approximation algorithm. We run ALG on some instance I with m machines and n jobs with processing times p₁,...,Pn. We find out that the cost (length) of the schedule found by the algorithm is more than 2 times the value Σ, p₁/m (which we know is a lower bound on the optimal value.) (a) (2 points) Based on this information, can we conclude that professor Clever's claim must be false? Explain your answer. (b) (3 points) Now, the same question but with the additional information that Pj E {1,2} for each job in our instance I. (c) (3 points) Again, the same question but with the additional information that Pj E {2,3} for each job in our instance I and n ≥ 5m.

Answer rating: 100% (QA)

a Yes we can conclude that Professor Clevers claim is false If his algorithm only had a 15factor app... View the full answer