. You are asked to consult for a business where clients bring in jobs each day for processing. Each job has some processing time ti that is known when the job arrives. The company has a set of 10 machines, and each job can be processed on any of those machines. Up until now, the company has been running the simple "minimize the makespan" approximation algorithm that we covered in lecture, which (as you will recall) always gives a 2-approximation. They’ve been told this may not be the best approximation algorithm possible, and they are wondering if they should be afraid of the performance. However, they are reluctant to change the scheduling, since it is simple and jobs can be assigned to a processor
as soon as they arrive. In particular, once you told them the makespan could be twice as large as optimal, they decided to analyze their performance and found a surprising fact: They have been running it each day for a month, and they have not observed it to produce a makespan more than 20% above the average load, 1
10 sumiti. To try to understand why they never hit a factor-of-two behavior, you ask a bit more about the kinds of jobs and loads they see. You find out that the sizes of jobs range between 1 and 50, so that 1 ≤ ti ≤ 50 for all i, and that the total load P i ti is quite high each day - always at least 3000. Prove that for these types of jobs, the makespan greedy approximation algorithm from class will indeed always find a solution whose makespan is at most 20 percent above the average (and hence optimal possible) load.