A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem

DOI10.1016/0022-0000(78)90026-0zbMath0397.68045MaRDI QIDQ1253918

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

Lower Bound; Knapsack Problem; Linear Search Tree Program

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R99: Discrete mathematics in relation to computer science

Related Items

The complexity of linear programming, Dispersion of mass and the complexity of randomized geometric algorithms, 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, Open problems around exact algorithms, Unnamed Item, On computations with integer division

Cites Work

• A lower bound on the number of additions in monotone computations
• Proving simultaneous positivity of linear forms
• Complete linear proofs of systems of linear inequalities
• A Lower Bound of the Number of Threshold Functions
• Unnamed Item
• Unnamed Item