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

DOI10.1007/BF00290735MaRDI QIDQ1052091zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A Lower Bound of the Number of Threshold Functions
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem

Cited in

(5)

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

This page was built for publication: A lower time bound for the knapsack problem on random access machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1052091)