Minimizing waiting time – Greedy Algorithms – 2
February 16, 2011 Leave a comment
Question.We are given n requests which need to be serviced. Assume that all requests are given to us at time t=0. It takes time, t [i] to service request i.
The waiting time of request , denoted by W[i] is defined as :
. (where the summation is over all requests serviced prior to servicing request i.)
We want to service the requests such that the total waiting i.e. the sum of the waiting times of the n requests, is minimized.
This is a simple application of the greedy paradigm.
As is intuitively clear, we would like to service shorter requests first, before moving on to requests with a larger t [i] value.
We make the intuition concrete as follows:
Sort the n requests in non-decreasing order of t[i] values.
Service the requests in this order.
Intuitive proof of correctness of algorithm:
Consider what happens when you have to decide which request to service, and there are more than one requests. Consider any 2 such requests. If you schedule the request with the larger t[i], it would mean that the other request would have to wait for that larger amount of time before being serviced, thus adding that large quantity to the total waiting time. On the other hand, in case you service the smaller request first, the addition to the total waiting time would only be equal to the t[i] value of the smaller request. Hence, whenever you have a choice, go for the request with the smaller t[i] value.
This directly translates to the above algorithm.