Exponential Lower Bounds on a Class of Knapsack Algorithms

DOI10.1287/MOOR.6.2.225MaRDI QIDQ3960469zbMATH OpenOpenAlexFDO

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)