The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).
Analysis of a Greedy Knapsack Heuristic I
Loading...
From the course by Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
378 ratings
From the lesson
Week 3
Approximation algorithms for NP-complete problems.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
Let's now turn to the analysis of our three step Greedy Heuristic for
the Knapsack problem and show why it has a good worst case performance guarantee.
So the goal was to prove that the value of the solution output by the three-step
greedy algorithm is always at least half the value of an optimal solution,
a maximum value solution that respects the knapsack capacity.
The key idea behind the analysis is a thought experiment in
which we use as a yardstick, an algorithm that gets to cheat.
Recall in step one of our greedy heuristic,
we short the items in non-increasing order in bang for
buck, that is via the ratio of the value over the size.
In step two 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 + 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 seven residual units of capacity in the knapsack, and
suppose item k + 1 has size ten, then we envision taking 70% of item k + 1 and
filling up the knapsack with that fraction.
The value, let's say it's prorated, so
let's 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, imagine you have a knapsack of
capacity three and you had two items, both of size two.
Let's say one has value three and one has value two.
Well then in the greedy fractional solution you begin by considering item one
that has the higher ratio of three halves, that fits fully into the knapsack.
Then you move on to item two, it only fits 50% into the knapsack, and
the total value of the solution would be the full value of item one,
that's 3 plus 50% of the value of item two, so that add one more.
So the value of the greedy solution here would be four.
The greedy fractional solution would be four.
In the next quiz, I'm going to ask you to ponder what properties this greedy
fractional solution has relative to feasible of the knapsack instance.
The correct answer is D, the greedy fractional is always at least as good as
the best nonfractional solution and in fact it can be strictly better.
Indeed if you look at the last slide in that simple two 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,
cause 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 that is no way that could be better than optimal non fractional solution.
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 an 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 is really what it is.
One way you can prove this formally is using an exchange argument,
that's what I'll sketch on 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 wait of some of completion times
of a bunch of jobs on a single machine.
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 it s.
This is a subset of items that fit into the knapsack.
So you can imagine for example, a scenario in which the greedy fractional solution
packs item number one, and then item number two doesn't fit into the knapsack,
but if we take 80% of item number two then that fully fills up the knapsack.
So that might be the greedy fractional solution and maybe we're thinking about
a non-fraction solution where item one is equally well packed there, but
instead of item two, which wouldn't fit, it uses item four which is smaller.
And maybe there's some little bit leftover of unfilled knapsack capacity for
this non-fractional solution, capital S.
So the interesting case is where S packs some stuff that the greedy fractional
solution does not and let's suppose it uses up L units of the knapsack capacity
via items which are not packed by the greedy fractional solution.
Well on the other hand,
the greedy fraction solution completely fills up the nap sack.
It uses all the space, all capital w units.
So if there's L units of stuff in S, which are not in the greedy fractional solution,
they'll have to equally be at least L units of stuff
in the greedy fractional solution, which are not packed by S.
So this might make it seem like the two 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-per-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
capital 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 of S.
Since S was arbitrary that shows that the greedy functional solution is in some
sense better than optimal.
It's better than all the non-fractional feasible solutions.
Now it's not clear though why you want to worry bother to do this thought
experiment, which transpired in some fantasy world where we were allowed to
pack items fractionally.
Now what we really care about is our three step greedy algorithm,
and that's not in the fantasy world.
That's in a real world where we cannot pack items fractionally.
So what good could this thought experiment experiment be?
Well, as we'll see in the analysis in the next slide,
it provides a useful yard stick.
A hypothetical bench mark against which we can compare the performance of our
three-step greedy algorithm
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
