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
4.2 Scheduling to Minimize Lateness: An Exchange Argument
The Problem We have a single resorce, and a set of job requests with a start time and a deadline. We are trying to schedule the tasks to minimize the max lateness.
opt Algo: Earliest deadline first.
The main step in showing the optimality of our algorithm is to establish that there is an optimal schedule that has no inversions and no idle time.
analysis: Our plan here is to gradually modify O while preserving its optimality at each step, but eventually transforming it into a schedule that is identical to the schedule A found by the greedy algorithm. We refer to this type of analysis as an exchange argument
There is an optimal schedule with no idle time. All schedules with no inversions and no idle time have the same maximum lateness. Def. An inversion in schedule S is a pair of jobs i and j such that: di < dj but j scheduled before i.
