Parallel approximation schemes for subset sum and knapsack problems (Q1084863)

This paper presents parallel approximation schemes for the Subset Sum, 0- 1 Knapsack, and several other optimization problems. These algorithms offer a three-way trade-off among parallel time, the accuracy of the solution and the number of processors used. The maximum numbers of processors which can be usefully employed depend on n (the size of the input), and the accuracy requirement \(\epsilon\). The parallel running times of the algorithms are polynomial in both log n and log(1/\(\epsilon)\) when enough processors are used.