Previous slide
Next slide
Toggle fullscreen
Open presenter view
CompSci 260P: Week 7
Greedy Algorithms
Ryuto Kitagawa
University of California, Irvine
Before We Begin
Greedy algorithms make
greedy
choices
Making optimal decisions based on local information
Recall in Dynamic Programming, we break the problem down into making a single choice
Dynamic programming looks at the choice and uses recursion to find the optimal
Greedy algorithms instead make the optimal choice without recursion
The burden of greedy algorithms is in the
proof
!
Algorithmic Pizza
You are the manager and have
pizza orders
Making a pizza is divided in two stages:
Preparation
Baking
Order
takes
time in prep and
time in baking
Your oven is infinitely large, but you can only prep one pizza at a time
What order should you prep the pizza such that the last pizza comes out of the oven as soon as possible?
Algorithmic Pizza: Solution
It is tempting to start with an algorithm, then prove it
However, proofs can guide our algorithms instead
Notice this is a
permutation
problem
Therefore, what happens if we swap adjacent pizza orders?
Let's look at two consecutive orders
and
Algorithmic Pizza: Solution
Let
be how long it takes us to get to order
How long does pizza
and
take to get out of the oven?
What if we were to flip it?
How do we then use this information to find the optimal ordering?
Interval Scheduling Approximation
Given a set of intervals, find the largest subset of non-overlapping intervals
Algorithm:
Pick the shortest interval
Discard any overlapping intervals
Repeat until we have no more intervals
Prove this algorithm is a 2-approximation
Interval Scheduling Approximation
Consider the optimal solution and compare it to our own
What properties does the optimal solution have compared to our own?
The magic number to look for is 2
What happens when the optimal solution has more intervals than the greedy
Consider an interval that invalidates more than 1 interval
Can it invalidate more than 2?
No, because of the middle interval!
Interval Scheduling Approximation
For each interval, it can overlap at most 2 optimal intervals
Therefore, our solution is at most half of the optimal solution
Thus making it a 2 approximation