Minimizing waiting time – Greedy Algorithms – 2

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 i, denoted by W[i] is defined as :

W[i] = t[i] + \sum_{k} t[k]. (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.

Solution.

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.

——–

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: