Discrete Math

2. (12 points) Recall the load balancing problem from HW1: In computations over multiple processors, the load of a processor is the sum of the times of all loads assigned to that processor. To balance the computation, the goal is to minimize the maximum load across the processors. The input to the load balancing problem is a list of jobs, each labeled by the processor to each job In this HW, you'll explore the theoretical limits for balancing the load, depending on the input jobs given. Throughout, assume there are k processors Pi,..., Pk and n jobs ji,... .jn where n and k are positive integers. (a) Find a formula for the biggest theoretical value for the maximum load of a processor, as a function of the input list of jobs. Justify your formula. (b) Is there an algorithm which will always produce an assignment of jobs to processors that exactly yields this biggest maximum load? If so, give such an algorithm and explain why it has this property. If not, explain why not Note: such an algorithm would not do a good job of load balancing. (c) Prove that the minimum maximum load across all processors must be greater than or equal to Ji (d) Is there an algorithm which will always produce an assignment of jobs to processors that exactly yields this theoretical lower bound for the smallest maximum load (ie. the formula from part (c))? If so, give such an algorithm and explain why it has this property If not, explain why not