On Parallel Computation for the Knapsack Problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Jul 1982 English Publisher:Association for Computing Machinery (ACM)Journal:Journal of the ACM, volume 29, pages 898-903 (issn: 0004-5411, eissn: 1557-735X,

Copyright policy )

Authors: Andrew Chi-Chih Yao;

doi: 10.1145/322326.322342

On Parallel Computation for the Knapsack Problem

- Summary
- Subjects
- Metrics

Abstract

We are interested in the complexity of solving the knapsack problem with n input real numbers on a parallel computer with real arithmetic and branching operations. A processor-time tradeoff constraint is derived; in particular, it is shown that an exponential number of processors have to be used if the problem is to be solved in time $t \le {\sqrt{n}}/2$.

Related Organizations

University of California, Berkeley
United States
Stanford University
United States

Keywords

Analysis of algorithms and problem complexity, time-processor trade-off constraint, branching operations, Searching and sorting, Theory of operating systems

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	11
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average