Hello,
Suppose we want to add n numbers using multi processors. Each
of these numbers arrive at different time. The goal is to find a
scheduling such that the final sum can be computed as early as possible
(assume that each addition takes unit time). As can be verified easily
that the following greedy algorithm solves this problem optimally
Add (L = {t1, t2,...., tn}) // t1, t2, ...tn are the arrival
times of inputs
{
if (L has only one element)
return;
choose the two smallest value in L (say x and y), remove the two
values from
L and, insert 1 + max(x, y) in L. Call this new set as L'
Add (L' );
}
Now suppose that we have an advanced adder which takes less than unit
time to perform an
addition (Also it takes different amount of time to add two different
pair of numbers). For the simplicity we can also assume that we use
this adder only to add the base elements (i.e.,
all the intermediate sum values will be added using the normal adder
having delay of unit
time).
The nC2 (n choose 2) values which represent the delay of the advanced
adder on the pairs of
base elements are given as input. In this case how can we find the
optimal scheduling, or this
small modification moves the problem from the class P to the class of
NP-complete.
thanks in advance
Aj
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
