𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A lower time bound for the knapsack problem on random access machines

✍ Scribed by Peter Klein; Friedhelm Meyer Heide

Publisher
Springer-Verlag
Year
1983
Tongue
English
Weight
533 KB
Volume
19
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

✦ Synopsis

a.M. (Fed. Rep.) Summary. We consider random access machines which read the input integer by integer (not bit by bit). For this computational model we prove a quadratic lower bound for the n-dimensional knapsack problem. For this purpose, we combine a method due to Paul and Simon [1] to apply decision tree arguments to random access machines (with indirect storage access!) and a method due to Dobkin and Lipton [2] who proved the same lower bound for linear decision trees.

πŸ“œ SIMILAR VOLUMES

Lower Bounds for the Union–Find and the
Lower Bounds for the Union–Find and the Split–Find Problem on Pointer Machines
✍ Han La PoutrΓ© πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 490 KB

A well-known result of Tarjan states that for all n and m n there exists a sequence of n&1 Union and m Find operations that needs at least 0(m . :(m, n)) execution steps on a pointer machine that satisfies the separation condition. Later the bound was extended to 0(n+m. :(m, n)) for all m and n. In