~/Greedy Algorithms

Brandon Rozek

Photo of Brandon Rozek

PhD Student @ RPI studying Automated Reasoning in AI and Linux Enthusiast.

Greedy Algorithms are about making the best local choice and then blindly plowing ahead.

An example of this is documents on a tape. Let’s say to read any given document on a tape, you first need to read all the documents that come before it.

What is the best way to have the documents laid out in order to decrease the expected read time?

Answer: Putting the smaller documents first.

The book then generalizes it further by adding access frequencies. The answer to that is to sort by increasing length first and then decreasing access times.

Scheduling Classes

To maximize the number of classes one can take one greedy algorithm is to always select the class that ends first.

That will produce one maximal conflict free schedule.

Structure of Correctness Proofs for Greedy Algorithms

Hospital-Doctor Matching

Let’s say you have a list of doctors that need internships and hospitals accepting interns. We need to make it so that every doctor has a job and every hospital has a doctor.

Assuming we have the same number of doctors and hospitals and that each hospital offers only one internship, how do we make an algorithm to ensure that no unstable matchings exist?

An unstable match is when

The Gale-Shapley algorithm is a great greedy fit. It goes like this

  1. An arbitrary unmatched hospital A offers its position to the best doctor a who has not already rejected it.
  2. If a is unmatched, she tentatively accepts A’s offer. If a already had a match but prefers A, she rejects her current match and tentatively accepts the new offer from A. Otherwise a rejects the new offer.