First lets make our goal clear. We want a greedy algorithm that is

optimal in terms of reducing number of penalty events.

Assumption 1:

Given a list of n events with deadlines d1, d2, .., dn that are fully

ordered, no two events have the same deadline time stamp, in

another words 0 events with the same deadline time stamps, we

wish to prove our greedy algorithm performs optimally. By

definition of our problem time required to do these n tasks is n

units of time and based on our assumption 1, the time difference

between d1 and dn can not be less than n. So our greedy algorithm

performs optimally by doing the task with lowest deadline first.

This should be abvious.

Assumption 2:

Now assume for the given n events and their deadlines d1, d2, .., dn

there exists 1 event in the list with the same deadline as another. Without

the loss of generality lets assume these two events are at index i and i+1.

We have two cases.

Case 1: time difference between deadline at index i-1 and i+1 >= 2

Convince yourself that our greedy algorithm produces no penalities.

This also should be abvious. Because we have enough time to finish

the first i-1 events in time and at least 2 units of time to finish the two

events with the same deadline at indexes i and i+1.

Case 2: time difference between deadline at index i-1 and i+1 = 1

There are two cases here too.

Subcase 1: the time difference between start time and deadline at

index i-1 is > i-1 units of time

Then obviously our algorithm would finish the i-1 events ahead of

time with at least 1 unit of time to spare and that would result in

no penalties. You can not do better than no penalties.

Subcase 2: the time difference between start time and deadline at

index i-1 is = i-1 units of time

Then obviously our algorithm would finish the i-1 events just in

time with 0 unit of time to spare and that would result in 1 penalty.

Now use contradiction here to prove that there is no way you can

reschedule these events and still not generate at least 1 penalty.

Obviously you can not reschedule the first i+1 events and not

generate at least 1 penalty. Right?

Now you have the two assumptions for 0 and 1 events with the same deadline.

In the induction step, assume the k events and prove the k+1 events with the

same deadlines. You must consider all the cases and subcases here too. Just

follow the same approach to prove them.

"Jack Smith" <st*******@yahoo.com> wrote in message

news:20**************************@posting.google.c om...

Hello, any help appreciated with following problem. I figured out the

algorithm (I think), just having trouble proving it is optimal.

Suppose we are given n tasks each of which takes 1 unit time to

complete. Suppose further that each task has a deadline by which it

is expected to finish. IF a task is not finished by the deadline, a

standard penalty of $10 is applied. The problem is to find a schedule

of the tasks that minimizes the penalty. Develop a greedy algorithm

to solve the problem. Prove that the algorithm gives an optimal

solution.

The greedy algorithm I came up with is:

you schedule tasks to run in order of earliest deadline that has NOT

passed. Schedule the tasks whose deadline has passed to run in the

end.

let me demonstrate with an example:

task1 -> d1 = 1 (d1 = deadline for task 1)

task2 -> d2 = 1 (d2 = deadline for task 2)

task3 -> d3 = 2 (d3 = deadline for task 3)

The greedy algorithm would scedule the tasks as follows

time = 0 -> run task1

time = 1 -> run task3 (task2 has earlier deadline, but time = d2)

time = 2 -> run task2 ($10 penalty)

How do I prove the greedy solution is the optimal? Can I use

induction or contradiction? If so How?

Thanks