A lower bound of 1 2n^2 on linear search programs for the knapsack problem

DOI10.1016/0022-0000(78)90026-0MaRDI QIDQ1253918zbMATH OpenOpenAlexFDO

Authors Richard J. Lipton, David P. Dobkin

Publication date 1978

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(78)90026-0

zbMATH Keywords

Knapsack ProblemLinear Search Tree ProgramLower Bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites work

• A Lower Bound of the Number of Threshold Functions
• A lower bound on the number of additions in monotone computations
• Complete linear proofs of systems of linear inequalities
• scientific article; zbMATH DE number 3562512 (Why is no real title available?)
• scientific article; zbMATH DE number 3635497 (Why is no real title available?)
• Proving simultaneous positivity of linear forms

Cited in

(22)

• Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
• A lower time bound for the knapsack problem on random access machines
• Lower bound arguments with ``inaccessible numbers
• On the limits of computations with the floor function
• On selecting the k largest with median tests
• Comparisons between linear functions can help
• Test complexity of generic polynomials
• Verification complexity of linear prime ideals
• On the complexity of computations under varying sets of primitives
• A lower bound for randomized algebraic decision trees
• Simulating probabilistic by deterministic algebraic computation trees
• Rough analysis of computation trees
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Open problems around exact algorithms
• Time and space complexity of deterministic and nondeterministic decision trees
• On computations with integer division
• A geometrical method in combinatorial complexity
• Computation over algebraic structures and a classification of undecidable problems
• Lower bounds on algebraic random access machines
• On genuinely time bounded computations
• The complexity of linear programming
• Dispersion of mass and the complexity of randomized geometric algorithms

This page was built for publication: A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem

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