Abstract
By the method of region counting, a lower bound of n log2 nn queries is obtained onlinear search tree programs which solve the n-dimensional knapsack problem. The region counting involves studying the structure of a subset of the hyperplanes defined by the problem. For this subset of hyperplanes, the result is shown to be tight.
Original language | English (US) |
---|---|
Pages (from-to) | 69-73 |
Number of pages | 5 |
Journal | Journal of Computer and System Sciences |
Volume | 13 |
Issue number | 1 |
DOIs | |
State | Published - Aug 1976 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics