Parallel Solution of Extremely Large Knapsack Problems

Simple item page
dc.contributor.authorFerris, Michael Cen_US
dc.date.accessioned2012-03-15T16:50:13Z
dc.date.available2012-03-15T16:50:13Z
dc.date.created1989en_US
dc.date.issued1989
dc.description.abstractWe shall describe a parallel algorithm for solving the knapsack feasibility problem, also known as the subset sum problem. The use of a random branching technique is described and its implementation on a parallel processor is discussed. Computational results show this to be an effective method for solving large problems. Using this approach we have solved problems with as many as 2 million variables in an average of 800 seconds on the Sequent Symmetry parallel processor. Furthermore, a coarse parallelization overcomes some of the problems that are present when serial algorithms are used to solve the knapsack problem.�en_US
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationTR842
dc.identifier.urihttp://digital.library.wisc.edu/1793/59114
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleParallel Solution of Extremely Large Knapsack Problemsen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR842.pdf
Size:
1.25 MB
Format:
Adobe Portable Document Format
Download

Collections

CS Technical Reports