------=_NextPart_000_07D9_01C9982C.30DF66E0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Correctness proof for the Activities = algorithm=20 Greedy:

Correctness proof :

Invariant INV :

S is a prefix of some = optimal solution=20 T.

1) At the beginning, INV holds for any = optimal=20 solution, since the empty set is a prefix of any ordered = set.

2) Statement:

If = S was a=20 prefix of an optimal solution T, and Greedy added a to S, then S U {a} = is a=20 prefix of some optimal solution T'.

Proof:

<Drawing>: T: = (S=3D)=20 _____ _________ ______ < a' > (RPT=3D) = ____ =20 ________ ___

where RPT means "Right Part of = T"

Observe that the case shown at Drawing = is=20 representative (that is the single possible). Indeed, all activities in = T -=20 S should be righter than those in S, since S is a prefix of=20 T.

Case 1: a' =3D a.

Then, we set T'=3DT, = and the new S=20 =3D S U {a} is indeed a prefix of T'.

Case 2" a' is not a.

Then, we set T' =3D = T - {a'} U=20 {a}.

Let us prove that T' = is legal.=20 Of course, T - {a'} is legal as a part of T. It remains to show that a = does not=20 intersect with T - {a'} =3D S U RPT.

1. a does not = intersect S by the=20 algorithm.

2. Since a' precedes = RPT in T,=20 for any activity a''=3D(s",t") in RPT holds: f' =3D< s" . =

By the=20 choice of a in Greedy, holds: f =3D< f', since both of a and a' = participated in=20 the choice, and a has the earliest finishing time.

Hence,=20 for any activity a''=3D(s",t") in RPT holds: f =3D< f' =3D< s" , = as=20 required.

Let us check that T' = is optimal.=20 Indeed, |T'| =3D |T| -1 + 1 =3D |T|. Since T is optimal, also T' is = optimal.=20

Besides, S is a = prefix of T',=20 since a precedes RPT.

3) At the end of Greedy, by INV, S is a = prefix of=20 an optimal solution T. Assume to the contrary, that T - S is non-empty. = Then,=20 any activity in T - S could be added to S, a contradiction to the = finishing=20 condition of Greedy.

<end-of-proof>

Comments:

1) It is a dangerous source of errors = to use a=20 drawing that shows only one of the possible cases!!

2) Seemingly, when INV incudes the = requirement=20 "prefix", Auxiliary Statement C is extra. It could be useful, if we = would remove=20 the requirement "prefix" from INV, but both of them are not=20 needed. Nevertheless, I add the proof of that = statement:

Auxiliary Statement C:

Greedy produces activities = from the=20 left to the right.

Proof:

Assume to the contrary = that there is a=20 problem instance such that Greedy violates this property. Let us = consider the=20 *first* time during the executon when activity a=3D(s,f) added to S = satisfies the=20 wrong inequality f < s', where a'=3D(s',f') is = the rightmost activity=20 in S.

Notice that the previous choice was S = <-- S U=20 {a'} (since our case is the first wrong one). However, at the time of = that=20 choice, also activity a was available, and its finishing time was = earlier. Why a=20 was not chosen? -- a contradiction to the = algorithm.

<end-of-proof>

------=_NextPart_000_07D9_01C9982C.30DF66E0--