Adaptive Bin Packing with Overflow: Budgeted Greedy Has Expected Cost at Most (3 + 2√2) Times That of the Optimal Policy for I.I.D. Item SizesResearch Paper
Motivation
Sequential packing matters when an item's size is known statistically before placement but revealed only afterward. A connection request has uncertain bandwidth, a shipment has uncertain final weight, and a virtual machine has uncertain resource use. In each example, exceeding capacity can have a separate cost from opening another container. Perez-Salazar, Singh, and Toriello formulate this as adaptive bin packing with overflow and analyze policies that respond to observed sizes without seeing future outcomes (paper, §1.1–1.2).
The paper's i.i.d. result gives a fixed numerical guarantee for a simple online rule, even against the best adaptive policy that knows how many items will arrive. This mission formalizes that theorem and the policy comparisons on which its statement depends. The source is the pinned preprint arXiv:2007.11532v2; all page and result numbers below refer to that version.
Setting
There are items with independent, nonnegative random sizes . Each bin has unit capacity. Before placing item , a policy knows its distribution and the realized sizes and assignments of earlier items, but it does not know . Its choice is irrevocable. A bin becomes unavailable after its accumulated load becomes strictly greater than one. Opening a bin costs one, and breaking a bin adds penalty . A policy here is deterministic, nonanticipative, measurable, and feasible: it never puts an item into an already overflowed bin (paper, §1.2 and §3.1).
Let count bins opened by policy , and let count bins whose final load exceeds one. The policy's objective is
For a bin with current load , placing item incurs overflow risk . The risk of a bin is the sum of these quantities over items assigned to it. A policy is risk-budgeted at level if every bin's risk is at most . These terms are properties of the realized history before each assignment, not substitutes for the actual count .
Budgeted Greedy, the paper's Algorithm 1, uses risk budget with . At a round it considers an opened bin if its load is at most one and the new item's risk would keep total risk within the budget. It uses an eligible bin if one exists and opens a new bin otherwise. The paper leaves ties arbitrary; the formal rule chooses the lowest indexed eligible bin. When an item has , it cannot fit the budget even in a fresh bin. The algorithm still opens a new bin for it, so a separate heavy-item case is needed in the performance theorem (paper, §3.2 and Theorem 4.4).
Formalization targets
The central target is Theorem 4.4, also stated in Theorem 1.2. For i.i.d. nonnegative items and , Budgeted Greedy is an admissible policy and, for every admissible policy ,
The comparison with every is deliberate. The paper explains that an exact minimizer need not exist for continuous distributions; its notation includes arbitrarily good approximations. The universal inequality therefore expresses the same guarantee without presuming that an optimum is attained (paper, p. 8 and Theorem 4.4).
The milestone list follows the paper's stated intermediate results. Proposition 3.1 identifies expected broken-bin count with expected accumulated risk. Lemma 3.4 and Corollary 3.5 turn the risk budget into an expected cost bound. Theorem 4.1 states that every policy has a controlled-cost counterpart that isolates high-risk items and budgets every other bin. Lemma 4.3 compares the expected bin openings of Budgeted Greedy with all budgeted policies for i.i.d. items. The heavy-item estimates are taken directly from the proof of Theorem 4.4. An initial milestone states that the online algorithm actually induces a policy (paper, pp. 4, 8–14).
Significance
The theorem supplies an explicit bound for an online packing algorithm when overflow has a monetary penalty. Its comparator may adapt to past observations and know the finite horizon, so the guarantee concerns a strong benchmark rather than a fixed packing plan. The structural milestones are also useful separately: the risk identity describes how individual placement probabilities account for broken bins, while Theorem 4.1 connects arbitrary policies to the risk-budgeted class (paper, Theorem 1.1, Proposition 3.1, Theorem 1.2).
The mathematical result is proved in the cited paper. This mission supplies Lean statements and definitions but does not claim machine-checked proofs of the milestones or the goal. A completed development would give a reusable interface for adaptive bin assignments, product laws for independent sizes, measurable policy costs, and per-bin risk accounting. Those definitions could support later statements about other distributions or packing rules from the same paper.
Difficulty
An item's overflow event is revealed after its bin has been chosen, while the bin choice can depend on all earlier sizes. Consequently, multiplying an unconditional overflow probability by a simple occupancy count does not directly give the cost: the assignment and current load are random. The risk identity must account for this dependence. The comparison with an arbitrary adaptive policy is harder because that policy can interleave work across bins, whereas Budgeted Greedy follows a narrower budget rule. The i.i.d. assumption supports the expected-opening comparison, but does not make the random policy histories disappear (paper, §§3–4).
Formalization scope
Items and bins are Fin n, indexed from zero. This provides at most bins, enough for a sequence of items. The item laws form a product probability measure on real-valued outcome vectors; nonnegativity is a separate support hypothesis. In the i.i.d. statements every coordinate uses one law . A bin breaks at load , not at equality. The algorithm's risk test uses the exact real probability of . All costs are integrals of the bin-opening and bin-breaking counts, rather than definitions in terms of risk.
The model makes policy measurability explicit so these real integrals do not acquire Lean's default value for nonintegrable or nonmeasurable inputs. Policy feasibility is required on every outcome vector, including vectors outside the nonnegative support; this is a chosen extension of the paper's reachable-history convention. The model also fixes a lowest-index tie break. Algorithm 1 line 3 omits the load-at-most-one test stated in its preceding prose; the formal algorithm includes it. Lemma 4.3 is stated under , the condition needed for Budgeted Greedy itself to be budgeted and the case in which the paper uses that lemma. These choices are disclosed in the item descriptions and moderation notes (paper, pp. 9–10, 13–14).
The representation must retain the two actual random counts and ; defining cost from the risk sum would erase Proposition 3.1's content. The finite indexing, product measure, measurable sets, and Bochner integrals use Mathlib. Useful contributions include proofs of policy measurability, the per-bin expectation identity, the risk-budget comparisons, and the final approximation bound.
Selected references
- S. Perez-Salazar, M. Singh, and A. Toriello, Adaptive Bin Packing with Overflow, Mathematics of Operations Research, 2022. Formalization source: arXiv:2007.11532v2, pp. 2–14 and 33–35.