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

DOI10.1007/BF00290735zbMath0515.68037OpenAlexW2029328491MaRDI QIDQ1052091

Friedhelm Meyer auf der Heide, Peter P. Klein

Publication date: 1983

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00290735

zbMATH Keywords

computational modelrandom access machinesdecision tree argumentslinear decision trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Related Items

On the limits of computations with the floor function, On computations with integer division, Lower bounds on algebraic random access machines, Simulating probabilistic by deterministic algebraic computation trees, Lower time bounds for integer programming with two variables

Cites Work

• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• A Lower Bound of the Number of Threshold Functions
• Unnamed Item