Online bin packing competitive ratio

Imagine filling boxes of capacity one as objects arrive. Two objects of size 0.4 could share a box, leaving little room. If two objects of size 0.6 then arrive, that choice needs three boxes; knowing the future would let you pair 0.4 with 0.6 in two. Online bin packing asks how well a rule can do when it must place each object before seeing the next.[1] [2]

Each arriving item must be placed before the next size is known. A bin holds a total size of at most 1, and earlier placements cannot be changed. The offline optimum $\mathrm{OPT}(I)$ is the fewest bins needed for the complete input list $I$; $A(I)$ is the number used by a proposed online rule $A$. We seek its worst-case factor once packings are large enough that a fixed number of extra bins no longer controls the comparison. This asymptotic competitive ratio is

$$R_A=\lim_{N\to\infty}\sup_{I:\mathrm{OPT}(I)\ge N}\frac{A(I)}{\mathrm{OPT}(I)}.$$

The supremum selects the most unfavorable permitted list with an offline optimum of at least $N$ bins. Taking $N$ larger removes small-instance effects. The problem asks for $R^*=\inf_A R_A$, the smallest ratio achievable or approached by deterministic online rules. There is no polynomial running-time bound here: the cost counts bins, and the central restriction is missing future information.[1]

Even the best rule must sometimes waste space because it does not know what comes next. Researchers can guarantee fewer than about 1.57829 times the number of boxes a fully informed packing needs. They also know that every deterministic rule can be forced above about 1.54278. The exact best long-run guarantee between these bounds remains unknown for the classical arrival model.[1] [2] [3]

The published constructive guarantee is $R_{\mathrm{AH}}\le 1.57828956$, while a fully adaptive construction places the universal lower bound above $1.54278$. These are performance guarantees, rather than measurements on a dataset. Upper-bound analyses assign weights to items so an algorithm’s bin use can be charged to total weight and an optimal bin has bounded weight. Lower bounds must defeat every rule, including one that reacts to exact sizes. Closing this gap requires matching the two sides, or achievable ratios tending to the infimum if it is not attained.[1] [2]

The little example explains the conflict: packing tightly now can destroy useful space later, while reserving space can waste boxes if the arrivals stop. Neither instinct always wins. A solution would identify the precise cost of making irreversible choices without future information. It would also show whether the current sophisticated rules already capture everything that can be gained from watching the arrivals so far.[1] [2]

The order of quantifiers gives the claim its force: an algorithm must handle every input, whereas a lower-bound adversary can exploit the behavior of whichever deterministic algorithm is proposed. That adversary’s completed list can still be repacked optimally by the offline comparator. Parallel-copy algorithms evade a different restriction by retaining several incompatible decisions and choosing the best result afterward. Their ratios can cross the classical lower bound because the allowed information and commitment structure have changed.[2] [5]