Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Computing an optimal solution to the knapsack problem is known to be NP-hard. Consequently, fast parallel algorithms for finding such a solution without using an exponential number of processors appear unlikely. An attractive alternative is to compute an approximate solution to this problem rapidly using a polynomial number of processors. In this paper, we present an efficient parallel algorithm for finding approximate solutions to the 0-1 knapsack problem. Our algorithm takes an ε, 0 < ε < 1, as a parameter and computes a solution such that the ratio of its deviation from the optimal solution is at most a fraction ε of the optimal solution. For a problem instance having n items, this computation uses O(n 5 2/ε 3 2) processors and requires O(log3n + log2nlog( 1 ε)) time. The upper bound on the processor requirement of our algorithm is established by reducing it to a problem on weighted bipartite graphs. This processor complexity is a significant improvement over that of other known parallel algorithms for this problem. © 1991.
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Reena Elangovan, Shubham Jain, et al.
ACM TODAES
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000