Chapter 4

definition of Greedy agorithm: An algorithm is greedy if it builds up a solution in sma!l steps, choosing a decision at each step myopically to optimize some underlying criterion. OR Finding the best step locally.

Section Summary:

Problem Motivation: We have a set of requests {1, 2 ….. n}; the ith request corresponds to an interval of time starting at s(i) and finishing at f(i). We’ll say that a subset of the requests is compatible if no two of them overlap in time, and our goal is to accept as large a compatible subset as possible. Compatible sets of maximum size will be called optimaL.

• Most Natural attempt: select the available request that starts earliest.
• Result: not optimal ⇒
• Counter-Example: if the earliest request i is for a very long interval, then by accepting request i we may have to

reject a lot of requests for shorter time intervals

  
* attempt 2: smallest interval of time
* result: not optimal  * counter-example: p142 fig.b

• Optimal solution: choosing the request that finishes the earliest
• Proof of optimality: greedy stays ahead in each step.

A Related Problem: Scheduling All Intervals Interval Partitioning Problem

algorithm on P149

Proof Approaches:  Greedy algorithm stays ahead • Does better than any other algorithm at each step  Exchange argument • Transform any solution into a greedy solution  Structural Argument • Figure out some structural bound that all solutions must meet