thrifty_greedy_step
For a non-empty set of remaining timely items R with witness hR : R.Nonempty, thrifty_greedy_step R hR returns the TimelyBin whose trigger item is the minimal element p = R.min' hR under the linear order, whose packing time is p.deadline, and whose items consist of p together with the items from (R.erase p).filter (fun q => q.arrival ≤ p.deadline), sorted by (· ≤ ·), that fit into the remaining capacity 1 - p.size according to greedy_pack_list.
Statement
noncomputable def thrifty_greedy_step (R : Finset TimelyItem) (hR : R.Nonempty) : TimelyBin
- Defined in
- arXiv:2611.09611, Section 2
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 6
- instLinearOrderTimelyItemThe linear order on
TimelyItemobtained by pulling back the lexicographic order onℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝalong the injective function… - TimelyBinA structure
TimelyBinrepresenting a bin in timely bin packing, with fieldsitems : Finset TimelyItem(the finite set of items packed… - greedy_pack_listGiven a remaining capacity
remCap : ℝand a list of timely items,greedy_pack_list remCap : List TimelyItem → Finset TimelyItem… - TimelyItemA structure
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),… - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- instLinearOrderTimelyItemThe linear order on
- Used by 1
- thrifty_greedy_auxA fuel-bounded recursive procedure
thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBinthat, on remaining itemsR, returns…
- thrifty_greedy_auxA fuel-bounded recursive procedure
Read back from the Lean
thrifty_greedy_step defines a function that takes:
1. R : Finset TimelyItem, a finite set of timely items (where each item has fields id : ℕ, arrival : ℝ, deadline : ℝ, and size : ℝ), and
2. hR : R.Nonempty, a proof that R is nonempty,
and produces a TimelyBin (a structure with items : Finset TimelyItem and time : ℝ) constructed as follows:
- Let p be the minimum element of R with respect to the ambient linear order on TimelyItem (R.min' hR).
- Let t = p.deadline.
- Let pending be the subset of R \ {p} consisting of all items q whose arrival time satisfies q.arrival ≤ t.
- Sort pending in ascending order (using ≤) into a list pendingList.
- Greedily pack items from pendingList into a bin of remaining capacity 1 - p.size via greedy_pack_list: traversing pendingList in order, an item x is included if its size is at most the remaining capacity, after which remaining capacity is decreased by x.size; otherwise x is skipped. Let others be the finite set of items selected by this procedure.
- Return the TimelyBin with items equal to {p} ∪ others and time equal to t.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- One step of Thrifty-Greedy: open a bin for the earliest-deadline pending item and greedily fill it. -/ noncomputable def thrifty_greedy_step (R : Finset TimelyItem) (hR : R.Nonempty) : TimelyBin := open Classical in let p := R.min' hR let t := p.deadline let pending := (R.erase p).filter (fun q => q.arrival ≤ t) let pendingList := pending.sort (· ≤ ·) let others := greedy_pack_list (1 - p.size) pendingList { items := insert p others, time := t }