greedy algorithm

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

re: greedy algorithm

Nice homework assignment...

My suggestion would be to align the tasks so they exactly finish on their
deadline. From there, work with the overlaps. For each task calculate the
overlap count with other tasks. Start with the tasks with the highest
overlap count and see if there is room in further to the past where it can
be located without overlap. If so, move it back. If not, move it to the
future (after all other tasks) and accept a penalty. Repeat until no
overlaps remain.

Silvio Bierman

"Jack Smith" <stegen123@yahoo.com> wrote in message
news:20b84b19.0310222312.27184ffd@posting.google.c om...[color=blue]
> 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[/color]

re: greedy algorithm

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" <stegen123@yahoo.com> wrote in message
news:20b84b19.0310222312.27184ffd@posting.google.c om...[color=blue]
> 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[/color]

re: greedy algorithm

Your algorithm is correct.

The input is a list of n natural numbers.

The output of your algorithm is a re-arrangement of this list of
natural numbers, which I'll call S. Let S@i denote the ith element of
this list for 0 <= i < n. (Actually your output may be "run task1, run
task2" and such, but both forms are interchangeable)

If you were to write out the elements of S with their indices below
them, we can think of the indices as representing time.

Suppose that there is a re-arrangement T of the given list in which
more of the tasks finish on time than in S. It must be possible to
obtain T from S by swapping elements of S. In particular, we must swap
an element of S which finishes on time with one that does not if we
are to have any hope of increasing the number of tasks that finish on
time. Thus we are swapping an element of S, S@x with another element
S@y with S@x > x (corresponding task finishes on time) and S@y <= y
(corresponding task doesn't finish on time). Note that y > x since
according to our algorithm we "fill" S firstly with tasks whose
deadlines have not occured. If the number of tasks finished on time
increases after swapping then it must be that S@x > y and S@y > x, but
S@y <= y, so S@x > S@y, which is impossible, since y > x and we "fill"
S firstly with tasks of earliest deadline whose deadline has not
already elapsed, but S@y is a counter-example to this condition (since
at time x it's deadline has not occured and it's deadline is earlier
than the one for S@x). Thus we cannot improve on S, and so the
algorithm is optimal. []

I think that's correct anyway...



stegen123@yahoo.com (Jack Smith) wrote in message news:<20b84b19.0310222312.27184ffd@posting.google. com>...[color=blue]
> 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[/color]

re: greedy algorithm

On 23 Oct 2003, Jack Smith wrote:
[color=blue]
> How do I prove the greedy solution is the optimal? Can I use
> induction or contradiction? If so How?[/color]

This is sounding like you don't know how to prove the
correctness of an algorithm. My suggestion to you would be
to read your textbook or ask your teacher for an example of
a proof of correctness of some algorithm. You'll probably
want to read the proof of correctness for some greedy algorithm,
in particular.

J

re: greedy algorithm

"Jack Smith" <stegen123@yahoo.com> wrote in[color=blue]
> 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[/color]


Given any value for X, prove that you can prioritise tasks with less than X time units
and be atleast as efficient.

Assume you select a value greater than X,
then there can be several tasks that reach deadline earlier than X.[color=blue]
>x, <x1, <x2, <x3 ... <xn[/color]

A task will be penalised if n > X
A substitution between >x and a <x can only improve the result.
<x1, >x, <x2, <x3 ... <xn

A task will be penalised if n-1 > X,
since the >x does not have to terminate within X.
Therefore when X = n - 1 only the 1st situation will cause a penalty.

i.e. there is no benefit to selecting >x, since it works for all values of X, X=1, X=2,
selecting the smallest task first will avoid the penalty in the most cases.

Herc

re: greedy algorithm

"Jack Smith" <stegen123@yahoo.com> wrote in message
news:20b84b19.0310222312.27184ffd@posting.google.c om...[color=blue]
> 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[/color]

To show that the above solution is the optimal one, think of the special
case whereby there is only one task at each deadline value:

So 6 tasks with the following deadlines:

1
2
3
4
5
6

It is obvious that none of these tasks will go to penalty if the tasks are
run in the order of earliest deadline (whereas in reverse there will be 3
tasks that will go to penalty). With only one task at each deadline
expiry time, the scheduler can always keep ahead of the deadlines and so ALL
tasks will run without penalty.

So therefore we now need to consider the case where there are mulitple tasks

at some deadline expiry times. Taking the special case where there is at
least one task at
each deadline time tick, we could have 10 tasks with deadlines as follows:

1,
2,2,2
3,3
4
5,5
6

It can be seen that by running the tasks in reverse order (longest deadline
first) then only 4 tasks are saved from penalty, whereas running in the
forward direction allows you
to save one task at every deadline time tick (i.e saving a total of 6 tasks
from penalty).

In fact having one or more tasks expire at every time tick is the worst case
scenario for the scheduler, since then only one task can be saved each
tick.

However as soon as gaps apear between the expiry deadlines of the tasks then
this allows the scheduler to get ahead of itself and possibly start saving
some of the tasks which have duplicate deadlines.

E.g. 10 tasks with the following deadlines;

1
5,5,5,5,
8
9
10

The gap between the task with deadline 1 and the four tasks with deadlines 5
enables all the tasks to be executed without penalty.

So in summary by running the tasks in order of earliest deadline first the
following can be shown:

a) the maximum number of tasks that can ever be saved from penalty is equal
to the total number of ticks that are counted (i.e the same value as the
last deadline)).

b) The only way tasks can run to penalty is if there are multiple tasks with
the same deadline time.

c) The only way that multiple tasks with the same deadline time can be saved
from penalty is if there are gaps between the deadline times of earlier
tasks so that the
scheduler can get ahead of itself. In fact the total number of
'duplicate deadline' tasks
that can be saved at any time tick is equal to the difference between the
deadline of the current task and the current time tick (minus 1).