This is an old revision of the document!
Table of Contents
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.
4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
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