| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 837.1 | Conclusions & hand waving... | CHOVAX::YOUNG | Back from the Shadows Again, | Thu Mar 03 1988 19:40 | 41 |
| Several conclusions that I can see right away:
Let the set Gn be any collection of numbers whose 'Greedy' scheduling
on n processors results in a maximal ratio with the Optimal scheduling,
(ie. Gn is any set which demonstrates F(n) ).
1) If the largest Element of a set to be scheduled is >= 1/2 the
total sum of the set, then 'Greedy' scheduling will be equivilant
to the Optimal schedule. Therefore either Gn for some n does NOT
have any element >= 1/2 the sum of Gn, OR F(n) = 1 for that n.
Furthermore we can extend this to say that in cases where F(n) > 1
then ( Max(Gn) < 1/n ).
2) The largest 'error' that the Greedy algorithim can make on a
set to be scheduled is <= the smallest member of the set.
3) It is apparent that if the order of a set to be scheduled is
<= n, then the Greedy algorithim is equivilant to the Optimal solution.
It is also true, however, that the Greedy solution remains equivilant
to the Optimal solution so long as ( m <= 2n ) where m is the number
of elements to be scheduled.
4) Pulling 1, 2, & 3 together with .0 we can now conclude:
1 < F(n) < (1 + 1/(2n+1) )
Which is pretty good. Indeed I believe that I know the worst case
solution for n=2:
{ 3, 3, 2, 2, 2 }
Optimal: < 3 3 > = 6
< 2 2 2 >
Greedy: < 3 2 > = 7
< 3 2 2 >
If correct this means that F(n) = 1+1/7. Since 1 + 1/(2n+1) = 1+1/5
Then : 1 < 1+1/7 < 1+1/5 does confirm the theory.
-- Barry
|
| 837.2 | | CLT::GILBERT | Builder | Fri Mar 04 1988 13:58 | 25 |
| I'm not sure I agree. Consider:
[ 1 + (2n-2)/n ][ 1 ][ 1 ]
[ 1 + (2n-3)/n ][ 1 + 1/n ]
...
[ 1 + (n)/n ][ 1 + (n-2)/n ]
[ 1 + (n-1)/n ][ 1 + (n-1)/n ]
Versus:
[ 1 + (2n-2)/n ][ 1 + 1/n ]
[ 1 + (2n-3)/n ][ 1 + 2/n ]
...
[ 1 + (n)/n ][ 1 + (n-1)/n ]
[ 1 + (n-1)/n ][ 1 ][ 1 ]
This gives a ratio of (5n-2)/(4n-1).
For example, (scaling up to give integers)
4, 2, 2 vs 4, 3 => 8/7
3, 3 3, 2, 2
7, 3, 3 vs 7, 4 => 13/11
6, 4 6, 5
5, 5 5, 3, 3
|
| 837.3 | | CLT::GILBERT | Builder | Mon Mar 07 1988 10:45 | 21 |
| I've improved the bound to F(n) >= (4n-1)/(3n). The first few examples
(from which the pattern should be apparent) follow. I believe this gives
the worst ratio, but am looking for a proof.
3 2 2 vs 3 3
3 2 2 2 2
5 3 3 vs 5 4
5 3 5 4
4 4 3 3 3
7 4 4 vs 7 5
7 4 7 5
6 5 6 6
6 5 4 4 4
9 5 5 vs 9 6
9 5 9 6
8 6 8 7
8 6 8 7
7 7 5 5 5
|
| 837.4 | Ooops, again... | PLDVS2::YOUNG | Back from the Shadows Again, | Mon Mar 07 1988 12:54 | 32 |
| re .2:
I realized after I entered it that I had made a mistake in .1.
(4) is the only one that is wrong, I keep getting my 'm's and 'n's
mixed up in this thing.
However, (1),(2), and (3) are still correct.
Summarizing:
1) Max(Gn)/Sum(Gn) < 1/n
2) Optimal_time(Gn) - Greedy_time(Gn) <= Min(Gn)
3) Order(Gn) >= ( 2n + 1 )
Prove:
F(n) = (4n - 1)/(3n) ( ?? )
Where:
n - Number of processors
F(n)- Maximum ratio of greedy scheduling time to optimal scheduling
time for n processors.
Gn - A set that demonstrates F(n)
-- Barry
ps. Does anyone know if this is a 'solved' problem?
|
| 837.5 | | CLT::GILBERT | Builder | Tue Mar 08 1988 11:18 | 24 |
| > 2) The largest 'error' that the Greedy algorithim can make on a
> set to be scheduled is <= the smallest member of the set.
Suppose that the optimal schedule has a little bit of 'slack' in
it -- that is, not all of the processors finish simultaneously.
Then a tiny additional task can be added (to fill part of this
slack) without affecting either the Greedy or Optimal schedule.
But somehow the 'error' must be larger than this.
You can show that there *exists* a Gn with this property that gives
a maximal ratio -- just the Greedy schedule for a given Gn, and
remove any tasks that were started after the start of the (longest)
task that determines the overall time of that schedule.
Let T be a collection of numbers with 'error' <= the smallest number in T.
Calling the smallest number 'b', we have:
Greedy(T) <= (Sum(T) + (n-1)b)/n, and
Optimal(T) >= Sum(T)/n.
So that:
Greedy(T)/Optimal <= (Sum(T) + (n-1)b)/Sum(T) = 1 + b(n-1)/Sum(T)
|