Question 10: (10 points) A company perform real-time scheduling of jobs on multiple servers. Once a batch of n jobs arrives they need to be allocated to servers. The company has two types of servers: mf fast servers and m, slow servers. Let m = mf+ms. Each job j takes time p; to process on a fast server, and time 3p; to process on a slow server. The goal is to minimize the makespan of the schedule. Currently, the company is using the following simple greedy algorithm (list scheduling) to schedule a batch of n jobs: Process the jobs in an arbitrary order. Assign the next job in the list to the server with smallest current load (if there is more than one server with smallest current load take the fastest). (a) (3 points) Give an example showing that algorithm the company uses does not get the optimal result. (b) (4 points) Prove that even though it is not optimal, this simple greedy algorithm is a 4-approximation algorithm. (c) (4 points) Try to find an a-approximation algorithm for the problem with a < 4. Remember to prove that your algorithm is an a-approximation algorithm, argue that it runs in polynomial time, returns a valid solution, and has an approximation factor at most a.