Introduction.
In this homework, you will think about a scheduling problem,
implement two simple greedy algorithms for it, and analyze the
algorithms with respect to their correctness and running time.
Devising a proper schedule satisfying a bunch of constraints and minimizing some measure of cost (or maximizing some measure of profit) is fundamental problem for many industries and organizations. For example, every semester the university assigns courses to classrooms and slots in the day, while aiming to satisfy a bunch of constraints including "no two courses should be assigned to the same classroom at the same time." Presumably, the university solves this scheduling problem with one of its aims being: maximize the number of courses that can be offered in each semester. Scheduling airline flights, scheduling FexEx dropoffs and pickups, scheduling the restocking of items in a WalMart store, scheduling "jobs" on an assembly line in a car manufacturing plant, etc., are all examples of complicated scheduling problems that companies routinely "solve."
Consider the following "toy" scheduling problem. You own a resource --- it may be a conference room, a supercomputer, or an electron microscope --- and many people request to use the resource for periods of time. A request takes the form: can I reserve the resource starting at time s and ending at time f? In other words, each request is an interval [ s, f]. Your goal is to accept a subset of the requests, rejecting all others, so that the accepted requests do not overlap in time. Assume that you get paid a fixed amount (say $1000) for each request you accept. Therefore, the goal is to maximize the number of requests accepted, thereby maximizing your profit.
Example: Suppose that the set of requests are:
[9:00, 12:00], [9:30, 10:30], [10:00, 11:00], [10:30, 13:00], [14:00, 16:00], [13:30,14:00], [9:00, 15:00]For concreteness, think of these requests as representing blocks of time in a day that people want to reserve your conference room for. The first person wants the room from 9 am to noon, the second person wants the room from 9:30 am to 10:30 am, etc. A solution to this problem, that will fetch you $4000 is to accept the requests
[9:30, 10:30], [10:30, 13:00], [13:30,14:00], [14:00, 16:00]and reject everything else. Note that the intervals do not overlap --- which means that you are not "overbooking" your resource, a practice that airlines have no qualms pursuing. There does not seem to be a way of satisfying more than 4 requests, so this solution with 4 satisfied requests is optimal.
Greedy Algorithms.
I will describe two greedy algorithms for the above problem.
An algorithm is greedy, if it builds up a solution in small steps, making a choice
that seems best at each step.
Taking this "short-sighted" view and trying to as best as possible at each step
and hoping that this will yield a good solution in the long run is what makes
these algorithms "greedy."
Typically, greedy algorithms will yield a
solution that satisfies the constraints of the problem, but may not always be optimal.
Here is pseudocode for the two algorithms. Both algorithms take a set I
of intervals that correspond to requests, and return a subset S of non-overlapping
requests.
The span of an interval [s, f] is simply its length, i.e.,
f - s.
Let I be a set of intervals and let x be an interval in I.
The degree of x with respect to I is the number of other intervals in
I that x overlaps with.
The GREEDY_SPAN algorithm greedily picks an available interval with smallest span,
whereas the GREEDY_DEGREE algorithm greedily picks an available interval with smallest
degree.
GREEDY_SPAN(I) Initialize S to be the empty set while(I is not empty): Pick from I an interval x with smallest span (ties are broken arbitrarily) Add x to S Delete from I all intervals that overlap with x return S
GREEDY_DEGREE(I) Initialize S to be the empty set while(I is not empty): Pick from I an interval x that has smallest degree with respect to I (ties are broken arbitrarily) Add x to S Delete from I all intervals that overlap with x return S
Things you should do.
>>> I = [[9,15], [9,12], [9.5, 10.5], [10,11], [10.5, 13], [13.5,14], [14,16]] >>> greedySpan(I) [[13.5, 14], [9.5, 10.5], [14, 16], [10.5, 13]] >>> I = [[9,15], [9,12], [9.5, 10.5], [10,11], [10.5, 13], [13.5,14], [14,16]] >>> greedyDegree(I) [[13.5, 14], [14, 16], [9.5, 10.5], [10.5, 13]]
What to submit.
You are required to submit 3 files in a zipped directory (hw8.zip).
The files are: