A nonlinear lower bound on linear search tree programs for solving knapsack problems

David Dobkin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)69-73
Number of pages5
JournalJournal of Computer and System Sciences
Volume13
Issue number1
DOIs
StatePublished - Aug 1976

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A nonlinear lower bound on linear search tree programs for solving knapsack problems'. Together they form a unique fingerprint.

Cite this