So in this video, we're going to revisit our greedy algorithm for minimizing the
wait and somewhat completion times. And we're going to give a more robust
more general correctness proof that also accommodates ties amongst the ratios of
the different jobs. The main reason I'm doing this is not
because you know, I think the result is, is so earth-shattering in its own right,
but rather to give you further examples of exchange arguments in action, in
particular outside of a proof by contradiction.
So let's be formal about our new more general correctness proof.
So we're again talking about the greedy algorithm which orders jobs by the ratio
of weight to the length. We're no longer assuming these are
distinct. So we can't really say decreasing order.
We'll say non-increasing order. And ties can be broken any way you want.
We'll prove the algorithms commit, correct, no matter how the ties are
resolved. So fortunately,, we'll be able to reuse
much of the work that we did for the previous correctness proof.
But actually, our overall proof plan is going to change a little bit.
we're no longer going to proceed by contradiction.
So here's the high level, here's the high level plan of that.
So as before, we're going to argue correctness on every separate instance,
so fix an arbitrary one. So, the notation will be similar to last
time, so on this input, we'll let sigma denote the output of our greedy algorithm
and then we'll let sigma star denote an arbitrary other competitor, any other
schedule of the jobs. So now, we're going to do is were going
to show that sigma, the output of our greedy algorithm, is at least as good as
sigma star, since sigma star was arbitrary, that means the greedy
algorithms output is at least as good as every other schedule, and therefore,
sigma has to be optimal. So, let's now fill in the details.
We're going to make a similar notational assumption as last time and that we're
going to assume that the greedy schedule is just 1, 2, 3, all the way up to n. And
again, that's a content free assumption, we can get away with it just by changing
the names of the jobs, changing notation. So, recall the proof plan, we have to
take any other competing schedule sigma star and show that it's no better than
sigma, show that sigma is at least as good as it.
So fix any such schedule sigma star, obviously, if sigma star is sigma, then
they're they same or just as good as each other so there's nothing to do.
Now, if sigma star is not the same thing as sigma, if it's not just the sequence
1, 2, 3, all the way up to n, we're going to reuse a key observation from our
previous proof, namely any schedule other than just 1 through n has to contain in
it a consecutive pair of jobs, i and j, where j is executed immediately after i
where i has the higher index. So now we argue similarly to last time.
What does it matter that's, one job has a higher index than another.
Well, that means it's further along in the ordering, which means its ratio can
only be smaller. Remember, the ratios are non-increasing,
they can only go down in the order. So higher index, means lower ratio.
But there may be ties, so we can't claim a strict inequality, just a weak
inequality. And so again, by clearing denominators,
this boils down to the weight of job i times the length of job j is at most the
weight of job j times the length of job i.
Now, the next thing I want you to recall from our previous proof is that there are
nice semantics with wilj and wjli namely as the cost in the benefit of exchanging
jobs i and j in the schedule sigma star. So arguing as in the previous videos, we
can argue, we can claim that exchanging i and j [SOUND] from a schedule sigma star
has a net benefit, that is a benefit minus cost of wjli, that's because job
j's completion time drops by li minus wilj.
That's because job i's completion time increases by lj with this exchange and so
this is non-negative. [SOUND] So in comparison with our
previous proof, in our previous proof, with the assumption of bought us, it
bought us the stronger fact than we exchange i and j, in fact sigma star gets
strictly better. It's we get a better schedule than what
we started with. Here with ties, that need not be true.
If i and j have exactly the same ratio and we exchange them, then the cost
equals the benefit so the net change in the objective function is 0.
So we can only claim that by inverting i and j, we don't make sigma star worse.
It can only get better and might stay the same.
So let's see why that's good enough to nonetheless complete the proof.
So what the previous slide gives us, it gives us a method of changing a schedule,
massaging a schedule, so that, it doesn't get any worse, it can only get better.
Specifically, if we take any schedule sigma star, we take any adjacent
inversion, by which I just mean two consecutive jobs with the higher one
having a higher index. We exchange the jobs in any adjacent
inversion, we get a new schedule which can only be better.
Some of weighted completion times might be the same, but if it's different, it
has to be smaller. So in our previous proof, we knew it was
strictly better because we had no ties and then our proof by contradiction said
we were done. So what are we going to do now?
What we're going to do is take this operation, which massages the schedule
without making it worse, and we're just going to repeat it over and over and over
again, because actually, this operation has a
second property. Not only can it not make a schedule worse, but, it also decreases
the number of inverted job pairs. And here by an inversion, I mean the same
thing as when we counted inversions with the divide and conquer algorithm back in
part 1. I just need a job pair somewhere in the
schedule, where the higher next to one occurs earlier in the ordering.
When we exchange adjacent inversion, we uninvert that aversion and because they
are adjacent, we don't create any new inversions.
So the number of inverted job pairs drops by exactly one,
each time we do one of these exchanges. So what does that mean?
So here is the proof in a nutshell. We take an arbitrary competitor, some
schedule sigma star and we find, either it's the same as the greedy schedule.
If it's not, there is an adjacent inversion, in which case we exchange it.
We get a schedule that's at least as good and fewer inversions.
Either this new schedule is sigma, in which case we're done, or it's not, and
then we find an adjacent inversion, and we exchange it, it only gets better and
we keep going. Why can this not continue forever?
Well, the number of inversions can only be n choose 2 initially, that's if you
start with the schedule n, n - 1, n - 2, all the way 1 if the jobs are initially
backward. So, we can only do this exchange n choose 2 times before we
necessarily terminates witht the greedy schedule, 1 through n.
At that point what have we done? We've taken an arbitrary schedule sigma star,
we've massaged it, making it only better, and better, and better, and better,
terminating with our greedy schedule sigma.
What does that say? That says our greedy schedule sigma is at
least as good as when we started with sigma star.
So the greedy schedule is at least as good as this arbitrary schedule sigma
star, so it's optimal. It's better than
everything. So one final note before I write down the
QED. for those of you familiar with the bubble sort algorithm and it's totally
fine if you're not familar with bubble sort, but if you are familiar with bubble
sort, you will recognize that essentially what we're doing here inside the proof,
not in tour algorithm but inside our proof, we're applying bubble sort in
effect to this arbitrary competing schedule sigma star. And by uninverting
the inversion we transform it in to the, the greedy schedule, making it only
better, thereby justifying as optimal our greedy algorithm schedule sigma.