Improved heuristics for online bin packing
Improved heuristics for online bin packing is graded peer reviewed on whataifound.org, with the AI's role graded search scaffold.
FunSearch produced bin-packing heuristics outperforming standard baselines on benchmark distributions.
- Verification
- Peer reviewed
- Autonomy
- Search scaffold
- Lab
- Google DeepMind
- Model
- FunSearch (PaLM 2 / Codey)
- Field
- Computer science
- Date
- 2023-12-14
- Problem posed
- 1971 · open 52 yrs
- Notability
- 12 Wikipedia language editions
What was found
Discovered programs are human-readable, which allowed domain experts to inspect and deploy them. Practical rather than theoretical significance.
Novelty check
Compared against best-fit and first-fit families and published heuristics; improvements are empirical on tested distributions.
Caveats
An empirical improvement on benchmark distributions, not a proved worst-case bound.
Sources
Community discussion
How this is graded
whataifound.org grades every entry on two axes: verification (how solid the result is, from a machine-checked proof down to refuted) and autonomy (how much the AI did versus its human collaborators). This finding is peer reviewed and search scaffold. Full definitions are in the methodology.
Cite this entry
whataifound.org (2023). Improved heuristics for online bin packing. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2023-12-funsearch-binpacking