@don : still i didn't understand the logic .. 15th processor has to find the best possible case which includes all 4 items along with 36 items..is it not same as 40 items 0-1 knapsack?
On Wed, Mar 28, 2012 at 8:54 PM, Arun Vishwanathan <aaron.nar...@gmail.com>wrote: > Thanks Don! > > > On Wed, Mar 28, 2012 at 7:09 AM, Don <dondod...@gmail.com> 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 <aaron.nar...@gmail.com> 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 <dondod...@gmail.com> 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 <aaron.nar...@gmail.com> >> 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 algogeeks@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com. >> > > 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- **Regards * * <bagana.bharatku...@gmail.com> Bharat B | M.Tech II | C.S.E | IITM * * *Ph: +91 8056127652* -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
