CompSci 260P: Week 7

• 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!

Theorem 1

Testing

• You are the manager and have pizza orders
• Making a pizza is divided in two stages:
  1. Preparation
  2. 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?

• 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

• 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?

• Consider if pizza is prepared then pizza
  • Pizza comes out after:
  • Pizza comes out after:
• Consider if pizza is prepared then pizza
  • Pizza comes out after:
  • Pizza comes out after:

• Let's see which pizza comes out earlier in the first configuration
  • Which is larger: or
  • We can simplify the above by canceling like terms: or
  • The above depends on the value of the variables, so let's consider when
  • Then we know that meaning pizza takes longer
  • Therefore, we take the time it takes for the longer pizza and compare it to the others

• Therefore, we compare to the times for when pizza is prepared first
• Let's first compare with the time of pizza (when pizza is prepared first)
  • and
  • Simplified for comparison we get, and
  • So we know that preparing pizza first takes longer in this comparison

• Now let's compare with the time of pizza (when pizza is prepared first)
  • and
  • Simplified for comparison we get, and
  • So again, preparing pizza first takes longer here as well
• Conclusion: When preparing pizza first always takes longer
• The same logic follows for

• 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

• 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!

• 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