So now let's turn our attention to proving the correctness of this Greedy
Algorithm that we devised that proportatedly minimizes the some of the
waited completion times. Let me remind you of the formal
correctness claim. The claim is that our second greedy
algorithm. The one which looks at the ratio of each
job. The ratio of the weight to the length and
sorts them in decreasing order, is always correct.
For every possible input, it ouputs the, the sequence of jobs, which minimizes the
weighted sum of completion times. And as promised, it wasn't hard to devise
the greedy algorithm. It's certainly not hard to analyze its
running time, which is N Log N. The same time as sorting,
but it is quite tricky to prove it correct.
The way we're going to do that, is going to be our first example of what's called
an exchange argument, which is one of the few recurring principles in the
correctness proofs of greedy algorithms. So I'm actually going to give you proofs
of two different versions of this claim. Both will make use of an exchange
argument in slightly different ways. For starters that's going to be in the
next video and the next one. I'm going to make a simplifying
assumption that there are no ties amongst the ratios, that each job has its own
distinct ratio of its weight versus its length.
In this case, we will be able to get away with proof by contradiction.
So, on this slide lemme give you the high level proof plan and of how this is going
to go, we will start delving into the details on the next slide.
So on the high level we're going to begin by fixing an arbitrary instance.
By which I mean, you know just the description of the
weights and lengths that. So remember, we have to prove that our
algorithm is always correct. So we just fix an arbitrary instance, and
prove correctness on this arbitrary instance.
So, as I said, for the case with no ties, we're going to proceed by contradictions.
Remember, this means we assume what we're trying to prove is false.
And from that, we derive something which is obviously false inconsistent.
So, what would it mean to assume that this claim is false?
It means there exists an instances for which this greedy algorithm does not
produce an optimal solution. For which there's some other solution not
output by the greedy algorithm, which is better than that of the greedy algorithm.
So let me just give you some notation to set this up.
We're going to let sigma denote the greedy schedule.
And if our claim is false, that means this is not an optimal schedule there's
some other one which is better so call this better optimal sigma star.
So, to complete a proof by contradiction, we need to derive something which is
obviously false and the way we're going to do that here might strike you as
initially as a little weird but it turns out to work really well in this context.
From this assumptionm that the greedy algorithm is not optimal, and there is a
better scheduled sigma star, we're actually going to exhibit yet another
schedule which is even better than sigma star.
Strictly smaller picto.function value than sigma star has.
Why is that a contradiction? Well, by assumption, sigma star is
optimal so if you show that there is something even better than sigma star,
sigma star is not optimal and that completes the proof by contradiction.
So now lets start filling the details of this proof plan and making it rigorous.
So as I said in this video and the next we're going to be assuming that all of
the ratios are distinct. In general, of course that need not be
true and I'll give you a separate argument to handle the case of ties.
I'm going to make a second assumption. But, unlike the first assumption, the
second assumption has no content. It's just an assumption about notation.
I'm going to assume by renaming jobs, that job one, number one, is the one with
the highest ratio. Job number two is the one with the second
highest ration and so on. Job ending the one with smallest ratio.
As a consequence of this switch in notation the greeter schedule is very
simple to describe. It just schedules job one first, then job
two second, then job three third, and so on, all the way up to job N.
Okay, so we have one assumption which is not without loss of generality, and we'll
have a separate argument for handling ties.
We have a second assumption which is without loss of generality.
It's just an agreement amongst friends who want to minimize notation.
And now, lets actually derive something with content.
So given that the greedy schedule is just the jobs in order, one, two, three, all
the way up to N. And given our assumption that the greedy
solution is not optimal, and instead there's some other distinct optimal
schedule sigma star. I claim that sigma star must contain
consecutive jobs, that it is somewhere in the schedule, sigma star, I can isolate a
pair of jobs, one executed after the other, such that the earlier of those two
consecutive jobs has a larger index. I'm going to call these jobs I and J with
I being earlier. So again by virtue· of the optimal
solution sigma star being something other than the schedule one, two, three up to N
there must be two jobs somewhere in the schedule executed in a row one after the
other so that the earlier job I has a higher index then the subsequent job J.
Why is this true? Well the reasoning is that, the only
schedule. It has the property that indices only go
up as you go from the earliest job to the latest job.
The only way that indices will always go up is if you schedule the jobs one, two,
three, all the way up to N. There is no other schedule with a
property that indices always go up other than one, two, three, all the way up to
N. So this is an observation that's going to
be important in the rest of the proof, so make sure you pause, give yourself enough
time to stare at it and commit yourself it is in fact true.
Any, any schedule other than one, two, three, all the way through N, have to
have consecutive jobs, the earlier one having a higher index than the later one.
So I'm now in a position to explain the exchange in the exchange argument.
So let me just distill the two key points from the discussion so far.
So first of all we have changed notations so that ratios are decreasing with index
and this is exactly the same as the schedule that the greedy algorithm will
output. And then assuming that the optimal
schedule sigma star is something else we know it has consecutive jobs with a
earlier one having a higher index. Keep in mind, our high level proof plan
from the first slide of this video. Where, we're doing a proof by
contradiction. We need to derive a contradiction and
what we're going to do is we're going to exhibit a schedule even better than sigma
star thereby contradicting it's purported ophthalmology.
So how do we do that? We do that with an exchange.
So this exchange is going to take the place of methodic experiment.
We're going to take this purportedly optimal schedule sigma star and we're
going to switch the order just of the two jobs I and J leaving all of the other
jobs unchanged. So sigma star consists of various jobs.
It's called stuff collectively. then next is job I and after that
immediately is job J. And then there's possibly some more jobs
that get executed after J. And remember, we observe that, we can
chose I and J so that I has a higher index than J despite being scheduled
earlier. Then we execute this exchange.
The stuff before INJ is the same as before.
The more stuff after JNI, is the same as before.
But we're going to have them occur in opposite order.
And the key thing we have to understand next is, what are the ramifications of
this exchange? What are the costs?
What are the benefits? That's how we'll begin, the next video .