Exponential Lower Bounds on a Class of Knapsack Algorithms

DOI10.1287/MOOR.6.2.225zbMATH Open0496.90058OpenAlexW1969691008MaRDI QIDQ3960469FDOQ3960469

Authors: Dirk Hausmann, Bernhard Korte, R. Kannan 

Publication date: 1981

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.6.2.225

zbMATH Keywords

computational complexitygreedy algorithmexponential lower boundsNP- hardnessalgorithms having restricted access to the inputnonexistence of polynomial knapsack algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Boolean programming (90C09)

This page was built for publication: Exponential Lower Bounds on a Class of Knapsack Algorithms

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