Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.

James M. Calvin Joseph Y.-T. Leung

Published in: Oper. Res. Lett. (2003)

Keyphrases

greedy algorithm
knapsack problem
average case
worst case
greedy algorithms
greedy heuristic
dynamic programming
np hard
optimization problems
objective function
linear programming relaxation
optimal solution
greedy strategy
exact algorithms
cross validation
sample size
lower bound