zhuting

The Greedy Paradigm

Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end.

Features and Bugs of the Greedy Paradigm

  • Easy to come up with one or more greedy algorithms
  • Easy to analyze the running time
  • Hard to establish correctness

Warning: most greedy algorithm are not always correct.

A Scheduling Problem

In scheduling, the jobs have different length, which is the amount of time required to process the job, also each job has a weight, with higher weights corresponding to higher-priority jobs.

These two scoring functions lead to two different greedy algorithms:

  • GreedyDiff: schedule the jobs in decreasing order of (weight — length)
  • GreedyRatio: schedule the jobs in decreasing order of (weight/ length)

--

--