Thanks Don! On Wed, Mar 28, 2012 at 7:09 AM, Don <[email protected]> wrote:
> Let's say that you have 16 processors. You are trying to solve the 0-1 > knapsack problem for 40 items. > Each item i has size S[i], and you need to find the subset of items > which sums as close to T as possible without exceeding T. > > Pick four of items. There are 16 possible combinations of those items: > 0000 (none of those 4 items included) > 0001 (only item #1 included) > ... > 1111 (all four items included) > > You will essentially ask each of the 16 processors to solve the > knapsack problem for 36 items, starting with one of the 16 possible > combiations of the 4 items. Processor 0 will start with none of the > first 4 items. Processor 15 will start with all of them, and the other > processors will start with a different subset of the items. It may > seem like solving the problem for 36 items is not much different than > 40, but it requires 1/16th of the work. When each processor is done, > it knows the best solution including its assigned items from among the > first 4 items. To find the overall best solution you just need to > compare the 16 solutions and pick the one best. > > A possible improvement is to divide up the problem into more parts and > farm them out to the processors as they become available. This would > work better if you don't have a power of 2 number of processors. It > also would reduce the tendancy for some processors to finish early and > sit idle while one or two take longer to finish their portion of the > work. > > Don > > On Mar 28, 9:51 am, Arun Vishwanathan <[email protected]> wrote: > > @Don: I am not clear with your explanation. Please can you give me an > > example? > > > > > > > > > > > > On Wed, Mar 28, 2012 at 6:19 AM, Don <[email protected]> wrote: > > > If you have n processors, start with the n possible ways to select > > > from log2 n items. Assign each processor to find a solution based on > > > the resulting subset of remaining items. Each processor should be able > > > to work fairly independently, and when they are done, they can compare > > > results and find the best one. > > > Don > > > > > On Mar 27, 10:47 pm, Arun Vishwanathan <[email protected]> wrote: > > > > Hi all, > > > > > > I am planning to implement a parallel version of the 0-1 knapsack > > > problem. > > > > I tried reading up a bit and there are few suggestions here and > there. > > > > However I would like to know if anyone has an idea or links that I > cud > > > > refer for this? The main problem in parallelizing a DP algorithm is > the > > > > dependencies due to recursion? Is there an effective strategy for > this?? > > > > Using shared memory or message passing approach? > > > > > > Arun > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > "People often say that motivation doesn't last. Well, neither does > bathing > > - that's why we recommend it daily."- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- "People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
