mna4773-pc2

Goal This project looks at the concept of "quality-up" in parallel computing. The term "quality-up" refers to using parallelism to find a more accurate approximation of an NP hard problem. NP hard problems cannot be solved exactly within polynomial time. Many problems, however, have approximation algorithms that, while not guaranteeing an optimal solution, do provide an "approximately" optimal solution in polynomial time. This project looks at using parallelism to run many parallel copies of an approximation algorithm, and keeping only the best of the results. The hope is that, by running many parallel executions, we can find a more optimal solution in the same amount of time. Problem Description Click here to download PDF Status report 1 - Problem Description Please refer to the problem description. Additional Notes:

Code
ChartBuilder.java
ChartBuilder2.java
CSVBuilder.java
CSVBuilder2.java
Item.java
ItemList.java
ItemQueue.java
KnapsackExact.java
KnapsackHeuristic.java
KnapsackHyb.java
KnapsackPar.java
KnapsackSeq.java
Solution.java
Javadoc
allclasses-frame.html
allclasses-noframe.html
ChartBuilder.html
ChartBuilder2.html
constant-values.html
CSVBuilder.html
CSVBuilder2.html
deprecated-list.html
doc-files
help-doc.html
index-all.html
index.html
Item.html
ItemList.html
ItemQueue.html
KnapsackExact.html
KnapsackHeuristic.html
KnapsackHyb.html
KnapsackPar.html
KnapsackSeq.html
overview-tree.html
package-frame.html
package-list
package-summary.html
package-tree.html
resources
serialized-form.html
Solution.html
stylesheet.css
Results
Loosely Correlated
Tightly Correlated
Scripts
CSVresults.bat
Loosely Correlated
results.bat
Tightly Correlated
Timings
Loosely Correlated
Tightly Correlated