Improved heuristics for online bin packing
FunSearch produced bin-packing heuristics outperforming standard baselines on benchmark distributions.
- Model
- FunSearch (PaLM 2 / Codey)
- Field
- Computer science
- Date
- 2023-12-14
- Problem posed
- 1971 · open 52 yrs
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 and known objections
An empirical improvement on benchmark distributions, not a proved worst-case bound.
Nobody outside the lab has checked this yet.
Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Peer reviewed and Search scaffold.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Community discussion
Graded peer reviewed for verification and search scaffold for autonomy. What these mean.
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-binpackingBibTeX
@misc{whataifound-googledeepmind-2023-binpacking,
title = {Improved heuristics for online bin packing},
author = {{whataifound.org}},
year = {2023},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Google DeepMind. Verification: Peer reviewed. Autonomy: Search scaffold.},
url = {https://whataifound.org/finding/2023-12-funsearch-binpacking}
}