Fundamental algorithms
- Ordering
- Original arrival order
- Rules
- Next open bin, first feasible bin, or tightest feasible bin
- Algorithms
- Next-Fit, First-Fit, Best-Fit
Animation mode
Speed
0.75 s
Random-order seed
Example
Ready.
Ordering versus placement rule
Sorting and bin selection are separate design choices. The cards below isolate their effects.
Offline algorithms
- Ordering
- Nonincreasing item size
- Rules
- Apply Next-Fit, First-Fit, or Best-Fit after sorting
- Algorithms
- NFD, FFD, BFD
More algorithms
- Worst-Fit
- Choose the emptiest feasible bin
- Random order
- Randomly permute, then run Best-Fit
- MFFD
- Use size classes and specialized phases
Predict the next placement
Choose an algorithm and predict its next bin.
Fundamental algorithms
Next-Fit, First-Fit, and Best-Fit process the original input order.
Offline algorithms
Next-Fit-Decreasing, First-Fit-Decreasing, and Best-Fit-Decreasing sort before packing.
More algorithms
Worst-Fit, Best-Fit under random arrival, and an educational MFFD visualization.
Best-Fit random-order experiment
Run Best-Fit over many independent random permutations of the same multiset and inspect the empirical distribution.
The experiment reports the minimum, mean, maximum, and standard deviation of bins used. It is empirical and does not replace a random-order ratio proof.
Minimum—
Mean—
Maximum—
Std. dev.—
Run the experiment to generate a histogram.
Final comparison
Load an instance to see lower bounds and exact-OPT status.
Theoretical guarantees and standard runtimes
Classical worst-case results for unit-capacity one-dimensional bin packing. Runtime entries assume comparison-model implementations with standard search data structures.
MFFD note. The classical guarantee applies to the exact Johnson–Garey MFFD algorithm. The animation below uses a simplified, phase-based visualization for teaching and is explicitly not claimed to reproduce every implementation detail of classical MFFD.
| Algorithm | Model | Best-known guarantee shown here | Standard runtime | Primary source |
|---|---|---|---|---|
| Next-Fit | Online | Absolute/asymptotic ratio 2; in particular NF(I) ≤ 2OPT(I) − 1. | O(n) | Johnson et al. (1974) |
| First-Fit | Online | Tight absolute ratio 17/10: FF(I) ≤ ⌊1.7 OPT(I)⌋. | O(n log n); naive O(n²) | Dósa–Sgall (2013) |
| Best-Fit | Online | Tight absolute ratio 17/10: BF(I) ≤ ⌊1.7 OPT(I)⌋. | O(n log n); naive O(n²) | Dósa–Sgall |
| Next-Fit-Decreasing | Offline | Tight asymptotic ratio ≈ 1.69103. | O(n log n) | Baker–Coffman (1981) |
| First-Fit-Decreasing | Offline | Tight bound FFD(I) ≤ 11/9 OPT(I) + 6/9. | O(n log n) | Dósa et al. (2013) |
| Best-Fit-Decreasing | Offline | Tight asymptotic ratio 11/9; absolute ratio 3/2. | O(n log n) | Johnson et al. (1974) |
| Worst-Fit | Online | Absolute/asymptotic ratio 2. | O(n log n); naive O(n²) | Johnson et al. (1974) |
| Best-Fit, random order | Random-order | General asymptotic random-order ratio is strictly below 3/2; current lower bound ≥ 1.15582656. | O(n log n) per permutation | Hebbar–Khan–Sreenivas (2024) · Epstein–Levin (2025) |
| Modified FFD | Offline | Classical MFFD(I) ≤ 71/60 OPT(I) + 1. | O(n log n) | Johnson–Garey (1985) · Yue–Zhang (1995) |
Efficient implementations of First-Fit and Best-Fit trace back to Johnson’s “Fast algorithms for bin packing,” DOI 10.1016/S0022-0000(74)80026-7.
Ratios are asymptotic unless an absolute formula is explicitly stated. Additive constants matter on small instances.
Share and export
Encode the current instance in the URL, export summary data, save final packings, or print the page.