An alternative to Ben-Or's lower bound for the knapsack problem complexity

DOI10.1016/S0893-9659(01)00116-1zbMath1002.68064MaRDI QIDQ1609452

Valentin E. Brimkov, Stefan S. Dantchev

Publication date: 15 August 2002

Published in: Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

algebraic complexity of the knapsack problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Threshold arrangements and the knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Tight complexity bounds for the two-dimensional real knapsack problem
• Generalized Knapsack problems and fixed degree separations
• Real data-integer solution problems within the Blum-Shub-Smale computational model
• Lower bounds for arithmetic networks
• Some Remarks on the Foundations of Numerical Analysis
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: An alternative to Ben-Or's lower bound for the knapsack problem complexity