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

摘要

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.