__Theorem Th5.3-1__

**"T****he greedy algorithm always gives a best solution to the ordering projects by deadline
precedence problem."**

__Proofing__*:* Let's call **L** the solution we receive from the greedy algorithm,and **M** a best
solution.If **L****=****M**** **there is nothing else to prove,our job is done,so we consider the case that **L**
not equal to **M**.We must only show that we can make some changes in **M** and finally receive **L**
without a decrease of **M**'s total profit.

At first let's consider random common projects between **L** and **M,E****(****i****)****. E****(****i****)** belong in **L** as
well as in **M**.Let's also consider as **[t,t+1]&[t',t'+1]** the time unit in which the **E****(****i****)** project
is executed in** L** and **M** accordingly.If** t<t'** we transfer the execution time of **E****(****i****)** in** L** from **t**
to** t'**.Whichever project was supposed to be executed at **t'** time unit is transferred at t time unit.If
**t>t' **we do exactly the same in M .Now,the new order of execution in either **L** or **M** continues
not to abort out deadlines(can you tell why?).We can say that all common projects of **L** and **M**
are executed at the same time units.

Besides **L **not equal to **M** there is also that **L** is not a subset of **M** and **M **is not a subset of
**L**.If **L** was a subset of **M**,the greedy algorithm would not had finished.If **M** was a subset of **L**
than, **M** solution would not be a best one.Therefore,there are projects belonging to **L** and do
not belong to **M** and vice versa.We consider the set of projects,that belong to **L** and do not
belong to **M**,we call it:**L**-**M**.Out of this set we choose the one with the maximum profit
**E****(****a****)**.For all the projects **E****(****b****)** of the **M**-**L** set we can easily say that **P****(a)**>**P****(b)**,otherwise the
greedy method would have added the **E****(****b****)** project in L before **E****(****a****)**.Let's say that the **E****(****a****)**
project is executed at the** [t,t+1]** time unit.At the exact same moment another project **E****(****b****)** is
executed in **M**,and **E****(****b****)** does not belong in **L**,since the projects are executed simultaneously.If
we erase **E****(****b****)** out of **M**,and replace it with **E****(****a****)** the total profit of **M** does not decrease,and
those two solutions (**L** and **M** ) have one more common project.If we continue with the same
project we end up in **L** without decrement of the total profit of **M**.Therefore **L** is also best
solution.

HTML PAGE DIRECTOR :Papaioannou Panagiotis