CSCC73H3 Quiz: greedy-proofs
2 Mar 2017
School
Department
Course
Professor
Computer Science B36 Fall 2015
Scarborough Campus University of Toronto
Some comments on proving the correctness
of greedy algorithms
Vassos Hadzilacos
In class we proved the correctness of the greedy algorithm for interval scheduling by employing a “greedy-
stays-ahead” argument. Specifically, we proved that if the set of (compatible) jobs constructed by the
greedy algorithm listed left-to-right are
j1, j2,...,jk
and the jobs in an optimal set listed left-to-right are
j∗
1, j∗
2,...j∗
m,
then f(jt)≤f(j∗
t) for every t= 1,2,...,k. Using this, we then argued that the set of jobs produced by
the greedy algorithm is, in fact, optimal.
There is an alternative proof of a similar nature that uses what might be called the “promising set”
argument. Specifically, we prove that:
Lemma 1 For every iteration tof the loop, the set of jobs that have been added to the set Aat the end
of that iteration is a compatible set of jobs that is a subset of some optimal set.
Proof. By induction on t. The basis t= 0 is obvious, since at the end of the “0-th iteration” of the
loop, i.e., just before we enter the loop for the first time, Ais empty.
For the induction step, let Atbe the set of jobs in Aat the end of iteration t, for some t≥0. Assume
(by induction hypothesis) that Atis compatible and is a subset of some optimal set A∗of jobs. Let At+1
be the set of jobs in Aat the end of iteration t+ 1. We will prove that (a) At+1 is compatible, and (b) At+1
is a subset of some optimal set ˆ
Aof jobs. (Note that ˆ
Amay be a different optimal set than A∗.) Part (a)
is easy to see since the job added to Ain iteration t+ 1, if any, starts after all jobs in Athave finished.
Part (b) is likewise easy to see if no job is added to Ain iteration t+ 1, or if the job jadded to Ain
iteration t+ 1 happens to be in A∗. It remains to show (b) if some job jis added to Ain iteration t+ 1,
and j /∈A∗.
In that case, first we note that A∗contains some job j∗that conflicts with j: for, otherwise, we could
add jto A∗and obtain a set of compatible jobs with more jobs than A∗, contradicting that A∗is optimal.
Second, we note that A∗does not contain two jobs that conflict with j: for, otherwise, both of them would
start after all the jobs in Atfinished (because Atis, by induction hypothesis, a subset of A∗, which is
optimal and hence compatible), and one of them, call it j′, would finish before j; so the greedy algorithm
would have added j′, rather than j, to Ain iteration t+ 1. So, there is exactly one job j∗in A∗−At
that conflicts with j. Define ˆ
A= (A∗− {j∗})∪ {j}; in other words ˆ
Ais obtained from A∗by replacing
j∗with j. Since j∗is the only job in A∗that is conflicts with j,ˆ
Ais also a compatible set of jobs: jis
compatible with every job in At(otherwise it would not have been added to Ain iteration t+ 1 by the
greedy algorithm), and is compatible with every job in A∗−Atexcept for j∗. Furthermore, ˆ
Ahas the same
number of jobs as the optimal set A∗. So, ˆ
Ais optimal. Finally, by construction, ˆ
Acontains all the jobs
in Atas well as j. Thus, At∪ {j}=At+1 is a subset of the optimal set ˆ
A, as wanted.
1
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Some comments on proving the correctness of greedy algorithms. In class we proved the correctness of the greedy algorithm for interval scheduling by employing a greedy- stays-ahead argument. Speci cally, we proved that if the set of (compatible) jobs constructed by the greedy algorithm listed left-to-right are and the jobs in an optimal set listed left-to-right are j1, j2, . 2 , . j m, then f (jt) f (j the greedy algorithm is, in fact, optimal. t ) for every t = 1, 2, . , k. using this, we then argued that the set of jobs produced by. There is an alternative proof of a similar nature that uses what might be called the promising set argument. By induction on t. the basis t = 0 is obvious, since at the end of the 0-th iteration of the loop, i. e. , just before we enter the loop for the rst time, a is empty.
