.png){kind=icon}
Return
Fast and scalable parallel algorithms for knapsack-like problems
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1996.0150.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present two new algorithms for searching in sorted X + Y + R + S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n(2) log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n = O(2(s/4)), we obtain a new algorithm for solving certain NP-complete problems such as knapsack on s data items in time equal (up to a constant factor) to the best algorithm currently known. Each of the algorithms is capable of being efficiently implemented in parallel and so solving large instances of these NP-complete problems fast on coarse-grained distributed memory parallel computers. The parallel version of the heap based algorithm is communication-efficient and exhibits optimal speedup for a number of processors less than n using O(n) space in each one; the sampling based algorithm exhibits optimal speedup for any number of processors up to n using O(n) space in total provided that the architecture is capable of logarithmic time sorting. (C) 1996 Academic Press, Inc.
Keywords:
COMPLEXITY
SELECTION
MATRICES
COLUMNS
X+Y
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available
Cited Papers
No cited papers available