Re: greedy algorithm
From: bm (behzad_mortazavi_at_hotmail.com)
Date: 10/23/03
- Previous message: Silvio Bierman: "Re: greedy algorithm"
- In reply to: Jack Smith: "greedy algorithm"
- Next in thread: testing123_at_cfxweb.net: "Re: greedy algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 23 Oct 2003 12:14:40 GMT
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.com...
> 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
- Previous message: Silvio Bierman: "Re: greedy algorithm"
- In reply to: Jack Smith: "greedy algorithm"
- Next in thread: testing123_at_cfxweb.net: "Re: greedy algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
