Lets now turn to the analysis about a 3 step Greedy Heuristic for NAP set problem
and show why it has a good worst case performance guarantee.
So the goal is to prove that the value of the solution output by this 3 step greedy
algorithm is always at least half the value of an optimal solution, a maximum
value solution that respects the NAP set almost at capacity.
The key idea behind the analysis, is a thought experiment, in which we use as a
yard stick, an algorithm which gets to choose.
Recall that in, [COUGH] step 1 of our greedy heuristic, we sort the items in
non increasing order of bang for buck. That is, by the ratio of the value over
the size. In step 2 of the greedy heuristic, we
pack the items in this order. So maybe the first K items, for some
value of K in this order, fit into the knapsack.
But then we don't have room for item K plus 1, and at that point we stop this
step of the heuristic. The thought experiment is to imagine that
our algorithm gets to cheat and pack a fraction of this item k+1 into the
knapsack to fill it up fully. So for example, if we pack in the first k
items and after that, there's only 7 residual units of capacity in the
knapsack. And suppose item k+1 has size 10, then we
envision taking 70% of item k+1, and filling it, filling up the knapsack with
that fraction. The value, lets say it's prorated.
So lets say by, filling in 70% of the item into the knapsack, we get 70% of its
value. So we're going to call the output of this
cheating algorithm the greedy fractional solution.
So just to give a super simple example image a knapsack of copacity 3 and you
had 2 items both of size 2 you'd say 1 has value 3 and 1 has value 2.
Well then in the greddy fractional solution you begin by considering item 1
that has the higher ratio we have the fits fully in the napsack.
Then you move on to item 2, it only fits 50% into the knapsack, and the total
value of the solution would be the full value of item 1, that's 3, plus 50% of
the value of item 2, so that adds 1, 1 more.
So the value of the greedy solution here would be, 4.
The greedy fractional solution, would be 4.
[SOUND]. In the next quiz I'm going to ask you to
ponder, what properties, this greedy fractional solution has, relative to
feasible solutions Of the knapsack instance.
The correct answer is D, the greedy fractional solution is always at least as
good, as, the best non fractional solution, and in fact, it can be strictly
better. Indeed, if you look at the last slide in
that simple 2 item example, in that instance, the greedy fractional solution
is Better, strictly better than every single feasible solution.
Now, it's not going to be strictly better in every single instance, because there's
going to be instances where the greedy fractional solution happens to use no
fractions, it happens to just, fill the knapsack fully, using 100% of various
items. And then that, there's no way that can be
better than optimal, non fractional solutions.
So, I'm not going to prove this fact for you in gory detail, but let me give you
just an outline of the argument. So the claim, is that the greedy
fractional solution, of a knapsack instance, is guaranteed to be at least as
good, have at least as large a total value, as every feasible solution.
That is, every non Fractional solution. The proof of this would fit in
fantastically in the greedy algorithms section of this course.
That's really what it is. One way you can prove this formally, is
using an exchange argument. That's what I'll sketch at a high level
here. I'll leave it as an exercise to you to
fill in the details, but it's really very similar to our proof of optimality for
the greedy algorithm, for why, sorting by ratios minimizes the weighted sum of
completion times, of a bunch of jobs on a single.
[INAUDIBLE] So how should we proceed,we have to prove that the greedy fractional
solution is as good as every feasible solution, every non-fractional solution.
So fix such a solution, call is S. This is a subset of items that Fit into
the knapsack. So you could imagine, for example, a
scenario in which the greedy fractional packs item number 1.
And then, item number 2 doesn't fit, into the knapsack.
But if we take 80% of item number 2, then that fully fills up the knapsack, so that
might be the greedy fractional solution, and maybe we're thinking about non
fractional solution where Item 1 is equally well packed there, but instead of
item 2 which wouldn't fit, it uses item 4 which is small and then may be there is
some little bit left over of unfilled [INAUDIBLE] capacity for this
non-fractional solution S. So, the interesting case is where S
packed some stuff that the greedy fractional solution does not, lets
suppose it uses it uses l units of [INAUDIBLE] capacity via items which are
not packed by the greedy fractional solution.
Well, on the other hand, the greedy fractional solution completely fills up
the knapsack. It uses all of the space, all W units.
So, if there's l units of stuff in s, which are not in the greedy fractional
solution, there have to equally well be at least, l units of stuff in the greedy
fractional solution, which are not packed by it.
S. So this might make it seem like the 2
solutions are apples and oranges. Each of them packs some stuff that the
other one doesn't. But they're not apples and oranges, the
greedy fractional solution really is better.
Why? Well, by the greedy criterion everything not packed by the greedy
fractional solution, has ratio, has bang for buck Worse, than everything that it
did pack. So these l units that are missing from
the greedy fractional solution, are less valuable than the l units that it
includes. So, since the l units of stuff in the
greedy fractional solution, missing from S, are a better use of space, than the l
units of stuff that are in s, but not the greedy fractional solution.
Some, easy algebra shows that indeed, the overall value of the greedy fractional
solution, is at least the overall value. Value of S.
Since S was arbitrary, that shows that the greedy fractional solution is in some
sense better than optimal, its better than all of the non-fractional feasible
solutions. Now its not clear that women [INAUDIBLE]
bothered to do this thought experiment which transpired in some fantasy world
where we're allowed to pack items fractionally.
Now what we really care about is the 3 step greedy algorithm and that is not in
the fantasy world, that's in the real world where we cannot pack items
fractionally. So, what good could this thought
experiment [INAUDIBLE] be. Well, as we'll see in the analysis in the
next slide, it provides a useful yardstick, a hypothetical benchmark
against which we can compare the performance of our 3 step greedy
algorithm.