Random knapsack in expected polynomial time.

René Beier Berthold Vöcking

Published in: STOC (2003)

Keyphrases

knapsack problem
special case
dynamic programming
computational complexity
approximation algorithms
data sets
information systems
upper bound
worst case
uniformly distributed
machine learning
np complete
randomly generated