A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
From MaRDI portal
Publication:1253918
DOI10.1016/0022-0000(78)90026-0zbMath0397.68045OpenAlexW2920901117MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Lower bound arguments with ``inaccessible numbers, On the limits of computations with the floor function, On selecting the k largest with median tests, Rough analysis of computation trees, A lower bound for randomized algebraic decision trees, On genuinely time bounded computations, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Time and space complexity of deterministic and nondeterministic decision trees, Computation over algebraic structures and a classification of undecidable problems, Comparisons between linear functions can help, On computations with integer division, A geometrical method in combinatorial complexity, Dispersion of mass and the complexity of randomized geometric algorithms, Lower bounds on algebraic random access machines, Open problems around exact algorithms, Test complexity of generic polynomials, The complexity of linear programming, Verification complexity of linear prime ideals, On the complexity of computations under varying sets of primitives, Simulating probabilistic by deterministic algebraic computation trees, 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
Cites Work
