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

David Dobkin

doi:10.1016/S0022-0000(76)80051-7

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

David Dobkin

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

By the method of region counting, a lower bound of n log₂ 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	https://doi.org/10.1016/S0022-0000(76)80051-7
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

Access to Document

10.1016/S0022-0000(76)80051-7

Cite this

@article{457b0067b24f48c7ad264019ba7fe9d9,

title = "A nonlinear lower bound on linear search tree programs for solving knapsack problems",

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.",

author = "David Dobkin",

note = "Funding Information: by NSF Travel Grant DCR75-15624. Funding Information: * Portions of this research were supported by the ONR under Grant N00014-75-C-0450 and",

year = "1976",

month = aug,

doi = "10.1016/S0022-0000(76)80051-7",

language = "English (US)",

volume = "13",

pages = "69--73",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Dobkin, David

N1 - Funding Information: by NSF Travel Grant DCR75-15624. Funding Information: * Portions of this research were supported by the ONR under Grant N00014-75-C-0450 and

PY - 1976/8

Y1 - 1976/8

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/58149409281

UR - https://www.scopus.com/inward/citedby.url?scp=58149409281&partnerID=8YFLogxK

U2 - 10.1016/S0022-0000(76)80051-7

DO - 10.1016/S0022-0000(76)80051-7

M3 - Article

AN - SCOPUS:58149409281

SN - 0022-0000

VL - 13

SP - 69

EP - 73

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this