AI Proof WatchKeep up with AI contributions

Online one-dimensional bin-packing performance

In online one-dimensional bin packing, items arrive sequentially and must be placed in fixed-capacity bins without knowing future arrivals. How can an algorithm reduce the number of bins used, either on a specified input distribution or with a proved guarantee against the optimum?

Why it matters and what counts as progress

Why it matters: The problem studies packing decisions made with incomplete information and the gap between strong experimental performance and worst-case guarantees.

What counts as progress: Improve reproducible performance against matched heuristics on stated instances, or prove a better worst-case competitive ratio. Success on an experimental suite does not establish a competitive-ratio improvement.

How the problem developed

  1. 2002 · Upper bound [1]

    Andrew S. D. Seiden Harmonic++ achieved an asymptotic competitive ratio of at most 1.58889 for one-copy online bin packing.

  2. 6 Jul 2017 · Upper bound [2]

    János Balogh, József Békési, György Dósa, Leah Epstein and Asaf Levin Advanced Harmonic lowered the asymptotic competitive-ratio upper bound below 1.58, to 1.5783.

  3. 14 Dec 2023 · Empirical result [3]

    DeepMind researchers FunSearch produced online heuristics that beat First Fit and Best Fit on the reported OR-Library and sampled-distribution benchmarks; this is empirical performance, not a new worst-case ratio.

AI contribution

Mathematical discoveries from program search with large language models

Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi

The authors report packing heuristics that outperform tested baselines on their online one-dimensional bin-packing experiments.

AI involvementAI-centered
ImportanceModest
Technical verificationPartial
Human understandingFull
Paper date:

Read the contribution and its assessment →

Sources

  1. Andrew S. D. Seiden, On the online bin packing problem (2002)
  2. János Balogh, József Békési, György Dósa, Leah Epstein and Asaf Levin, A new and improved algorithm for online bin packing (2017; ESA 2018)
  3. S. Romera-Paredes et al., Mathematical discoveries from program search with large language models (2023)
  4. Original research paper
  5. Authors’ artifact
Website timeline

Publication dates and editorial changes.