Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
Edward G. Coffman Jr.Costas CourcoubetisM. R. GareyDavid S. JohnsonPeter W. ShorRichard R. WeberMihalis YannakakisPublished in: SIAM J. Discret. Math. (2000)
Keyphrases
- average case
- bin packing
- packing problem
- worst case
- learning curves
- worst case analysis
- competitive ratio
- maximum profit
- graph colouring
- integer programming
- np hard
- uniform distribution
- optimal solution
- lower bound
- search tree
- dynamic programming
- boolean functions
- knapsack problem
- learning problems
- multi dimensional
- average case complexity