Author |
Topic: Graham Scheduling (Read 1630 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Graham Scheduling
« on: Jul 15th, 2003, 1:03pm » |
 Quote  Modify
|
Came across this in a book... and liked it. If A is a set that includes only integers, let sum(A) denote the sum of the elements in A. For instance, sum({1,2,3}) = 6.
The scheduling problem is defined as:
Let m,n be two positive integers, and t be an array of n positive rational numbers. Partition the array into m disjoint subsets P1, ... , Pm so as to minimize maxj sum(Pj).
It is called the "scheduling problem" because it can be interpreted as the search for the best way to schedule n tasks of varying durations, given by t1, ... , tn, to m identical processors P1, ... , Pm. The best way is the way that will get them all finished as soon as possible.
This problem is known to be NP-hard even for m=2, and there exists a polynomial 2-approximation algorithm due to Graham that goes as follows (in pseudocode):
GRAHAM(m,n,t)
1.for j from 1 to m do Pj <-- empty set
2.for i from 1 to n do
3. begin-for
4. let Pk be the processor such that sum(Pk) is a minimum at the moment
5. Pk <-- Pk U {i}
6. end-for
7.return {P1, ... , Pm}
Put simply, when the algorithm has to schedule a task, it picks the idlest processor available and assigns the task to it. This is repeated for all the tasks. Now for the interesting part. Let opt(m,n,t) denote the best possible solution, the optimal solution for the input (m,n,t).
Note: I would rank difficulty as 3 < 1 < 2 < 4; 3 is 3 because it needs 1 and 2 to be understood properly.
1) Prove that this algorithm is in fact a 2-approximation; that is, prove that for all inputs (m,n,t) the schedule returned by GRAHAM takes time at most twice the time required by opt(m,n,t).
2) Better yet, prove that GRAHAM(m,n,t) takes at most 2 - 1/m times as long as opt(m,n,t) - so that for a single processor GRAHAM is an exact solution (duh) and for 2 processors it is off by at most 50%. For each m, show a possible input where GRAHAM is in fact off by the factor 2 - 1/m.
3) Let LOWCOST-GRAHAM be a variant of GRAHAM that works as follows. First, it sorts the tasks in non-decreasing order of duration, and then runs plain ol' GRAHAM on this new input. Show that this has absolutely no consistent effect by giving, for each m, an example of input where LOWCOST-GRAHAM is off by 2 - 1/m, same as GRAHAM.
4) Let GRAHAM-DELUXE(m,n,t) be the opposite variant of GRAHAM. First, it sorts the tasks in non-increasing order, and runs GRAHAM on that. Prove that GRAHAM-DELUXE is a (4/3)-approximation algorithm for the scheduling problem. Show a possible input where GRAHAM is off by the factor of 4/3.
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #1 on: Oct 29th, 2003, 3:13am » |
Quote Modify
|
I'm quite amazed  that no one have even tried to answer this question. So I'll be the first one... 
1) Quote:| Prove that this algorithm is in fact a 2-approximation |
|
Lets assume w.l.o.g that P1 has the maximal load at the end of the algorithm, lets (also) assume that the last task that was assigned to it, had T duration, and all the other tasks that were assigned to it had a total of W duration.
Now, it is quite easy to see that the load at each other processor is at least W (since o/w the task that was the last one to be assigned to P1 wouldn't have been assigned to it (contradiction to our assumption).). Therefore,
-> GRAHAM(m,n,t) = W + T
-> opt(m,n,t) [ge] (mW + T)/m [ge] max(W, T)
-> Approximation Factor = GRAHAM(m,n,t) / opt(m,n,t) [le] (W + T) / max(W, T) [le] 2.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #2 on: Oct 29th, 2003, 3:19am » |
Quote Modify
|
Here's another one  ...
2) Quote:| Better yet, prove that GRAHAM(m,n,t) takes at most 2 - 1/m times... |
|
We just need to analyze differently the expressions reached in the 1st question:
-> OPT = opt(m,n,t) [ge] (mW + T)/m = W + T/m
-> GRAHAM(m,n,t) =
W + T [le] OPT - T/m + T = OPT + (1 - 1/m)*T [le] OPT + (1 - 1/m)*OPT = (2 - 1/m)*OPT
-> Approximation Factor = GRAHAM(m,n,t) / opt(m,n,t) [le] (2 - 1/m).
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #3 on: Oct 29th, 2003, 3:24am » |
Quote Modify
|
As Pietro K.C. indicated this seems to be the easiest section  ...
3) Quote:| Show that this has absolutely no consistent effect by giving, for each m, an example of input where LOWCOST-GRAHAM is off by 2 - 1/m... |
|
An example of such input is 1,1,1,1...,m where the length of the 1's sequence is m(m-1).
-> opt(m,n,t) = m
-> LOWCOST-GRAHAM(m,n,t) = 2m - 1
-> LOWCOST-GRAHAM(m,n,t) / opt(m,n,t) = (2 - 1/m)
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #4 on: Oct 29th, 2003, 4:34am » |
Quote Modify
|
I'm stuck on the 4th question  ...
so the complete question is (yet) not solved !
Pietro K.C., This question is very nice  !!!
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Graham Scheduling
« Reply #5 on: Nov 10th, 2003, 6:15am » |
Quote Modify
|
Hi Dudidu!
I'm glad you enjoyed the puzzle.
I thought it was very nice too, but then no one gave it a shot, I started thinking I was weird... 
Your answers are great, really creative! I did #1 and #2 differently, but #3 was the same. Maybe I'll post it here later, but I haven't got the time now. Two finals this week...
Keep trying with #4, it's the nicest one! Good luck! And you can just call me Pietro, since we've grown so close now...
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #6 on: Nov 12th, 2003, 1:33am » |
Quote Modify
|
on Nov 10th, 2003, 6:15am, Pietro K.C. wrote:| Keep trying with #4, it's the nicest one! Good luck! And you can just call me Pietro, since we've grown so close now... |
|
Pietro hi,
Are you sure that GRAHAM-DELUXE is a (4/3)-approximation algorithm? it seems to be slightly better...
Quote:| Show a possible input where GRAHAM is off by the factor of 4/3. |
|
I've got an input that GRAHAM-DELUXE achieves (again) almost a (4/3)-approximation. Does this input is the desired one ?
Waiting ...
P.S. - Good luck with the finals .
|
| « Last Edit: Nov 12th, 2003, 1:41am by Dudidu » |
IP Logged |
|
|
|
Hello
Guest
|
on Oct 29th, 2003, 3:13am, Dudidu wrote:-> opt(m,n,t) [ge] (mW + T)/m [ge] max(W, T)
|
|
Sorry if I'm missing something, but where does the second inequality come from? Say, m=5, W=1, T=5:
W+T/m=2, max(W,T)=5.
|
|
IP Logged |
|
|
|
Hello
Guest
|
on Oct 29th, 2003, 3:19am, Dudidu wrote:OPT + (1 - 1/m)*T [le] OPT + (1 - 1/m)*OPT
|
|
Sorry again, please explain this too. You seem to be saying that T[le] OPT, but I don't find it obvious...
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #9 on: Nov 26th, 2003, 12:30am » |
Quote Modify
|
on Nov 25th, 2003, 5:09pm, Hello wrote:| Sorry again, please explain this too. You seem to be saying that T [le] OPT, but I don't find it obvious... |
|
Hello Hello ,
T [le] OPT reasoning:
T was defined as the duration of some single task, thus, in any scheduling (including the optimal) it must be assigned to a single processor [to] OPT will have a duration of at least T (T [le] OPT).
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #10 on: Nov 26th, 2003, 1:09am » |
Quote Modify
|
on Nov 25th, 2003, 5:04pm, Hello wrote:
Sorry if I'm missing something, but where does the second inequality come from? Say, m=5, W=1, T=5:
W+T/m=2, max(W,T)=5. |
|
I must admit that I don't understand this inequality and where it came from . However, I will fix it...
-> GRAHAM(m,n,t) = W + T [ge] opt(m,n,t) + opt(m,n,t).
-> Approximation Factor = GRAHAM(m,n,t) / opt(m,n,t) [le] 2.
Reasoning:
1) T [ge] opt(m,n,t) - same as the previous thread.
2) W [ge] opt(m,n,t) - since all the processors in the scheduling had at least W-duration tasks assigned to them then in OPT this must be also true (some kind of a "volume conservation").
Hopes this helps...
|
|
IP Logged |
|
|
|
NoMailPlease
Guest
|
on Jul 15th, 2003, 1:03pm, Pietro K.C. wrote:| 4) Let GRAHAM-DELUXE(m,n,t) be the opposite variant of GRAHAM. First, it sorts the tasks in non-increasing order, and runs GRAHAM on that. Prove that GRAHAM-DELUXE is a (4/3)-approximation algorithm for the scheduling problem. Show a possible input where GRAHAM is off by the factor of 4/3. |
|
|
|
IP Logged |
|
|
|
NoMailPlease
Guest
|
on Jul 15th, 2003, 1:03pm, Pietro K.C. wrote:| 4) Let GRAHAM-DELUXE(m,n,t) be the opposite variant of GRAHAM. First, it sorts the tasks in non-increasing order, and runs GRAHAM on that. Prove that GRAHAM-DELUXE is a (4/3)-approximation algorithm for the scheduling problem. Show a possible input where GRAHAM is off by the factor of 4/3. |
|
Sorry for the previous post. I'll use Dudidu's notation.
Consider the longest queue=W+T, where T is the last job scheduled to it. WLG we can say that it was the last job scheduled, because if there were jobs after it, we can remove them and it won't change the runtime of G-D, and may only decrease OPT. Now, T is obviously smallest of remaining jobs. So, we get:
GD = W+T <= OPT+T.
Now consider 2 cases:
(1) T<=OPT/3.
Then GD<4/3*OPT QED.
(2) T>OPT/3.
But other jobs must be only greater than T. This means there's at most 2 jobs per queue. Now it can be easily proved by a simple job-swapping argument that we can reduce an optimal schedule to GD without increase in runtime. It means that in this case GD gives exactly the same runtime as OPT. I'll omit this proof as it's too long-winded, I'm sure evrybody will see it if they think about it.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Graham Scheduling
« Reply #13 on: Nov 30th, 2003, 7:17am » |
Quote Modify
|
NoMailPlease, Bravo !
Your answer is correct and accurate.
A remark - in a similar way, we can improve this bound even better (i.e. bound of (4 / 3) - (1 / 3n)) and there is a very nice example of input, where GD is off by this factor (if nobody finds it, I will post it later).
P.S.
I know that I haven't posted this problem but still I want to acknowledge a good solution (I'm sure that Pietro would have done the same)...
|
| « Last Edit: Nov 30th, 2003, 7:18am by Dudidu » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove