Abstract
The complexity of solwng the knapsack problem with n input real numbers on a parallel computer wRh real arithmeUc and branching operations is considered A trine-processor trade-off constraint ts derived; m particular, it ts shown that an exponential number of processors have to be used if the problem is to be solved m time.
| Original language | English |
|---|---|
| Pages (from-to) | 898-903 |
| Number of pages | 6 |
| Journal | Journal of the ACM (JACM) |
| Volume | 29 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1 Jul 1982 |
Keywords
- Branching operauons
- complexity
- knapsack
- parallel computatmn
Fingerprint
Dive into the research topics of 'On Parallel Computation for the Knapsack Problem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver