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

DOI10.1007/BF00290735zbMATH Open0515.68037OpenAlexW2029328491MaRDI QIDQ1052091FDOQ1052091

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

• Title not available (Why is that?)
• 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

Cited In (5)

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

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)