Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
Edward G. Coffman Jr.Costas CourcoubetisMichael R. GareyDavid S. JohnsonPeter W. ShorRichard R. WeberMihalis YannakakisPublished in: SIAM Rev. (2002)
Keyphrases
- average case
- bin packing
- worst case
- packing problem
- learning curves
- worst case analysis
- competitive ratio
- online algorithms
- graph colouring
- online learning
- upper bound
- uniform distribution
- lower bound
- search tree
- constraint satisfaction
- image compression
- dynamic programming
- reinforcement learning
- average case complexity